개발해요

https://www.acmicpc.net/problem/1749

유형

누적 합, 완전 탐색

풀이

부분 행렬의 최대 값을 구하는 문제이다. 부분 행렬 or 배열에서 연속된 부분 합을 빠르게 구하는 방법으로는 누적 합이 있다. 일단 그것을 배제하고 단순하게 완전 탐색으로 모든 부분 행렬의 합을 구하려고 한다면, 아래와 같이 6중 for문을 사용하게 된다.

// 부분 행렬의 왼쪽 위 끝 점
for (startRow in 0 until rowSize) {
    for (startCol in 0 until colSize) {
        // 오른쪽 아래 끝 점
        for (endRow in startRow until rowSize) {
            for (endCol in startCol until colSize) {
                var partSum = 0
                // 부분 행렬 안에서 포인터 이동
                for (row in startRow..endRow) {
                    for (col in startCol..endCol) {
                        partSum += matrix[row][col]
                    }
                }
            }
        }
    }
}

시간 복잡도까지 안가도 이건 안되겠다는 게 느껴지지만ㅋㅋ, 대충 따져봐도 O(N^6)에 가깝기 때문에 이 방법으론 안된다.

위에서 얘기한대로 누적 합 방법을 사용하면 완전 탐색으로도 시간 안에 풀 수 있다. 누적 합이 위의 코드에서 맨 안쪽에 있는 실제 부분 합을 구하는 이중 for문을 수식 하나로 바꿔주기 때문이다. 즉, 부분 행렬의 시작 점과 끝 점만 알면 누적 합을 구하는 수식을 통해 O(1)로 합을 구할 수 있다.

ex) 부분 행렬 (2,3) ~ (5,7)의 합

= prefixSum[5][7] - prefixSum[2-1][7] - prefixSum[5][3-1] + prefixSum[2-1][3-1]

for (startRow in 0 until rowSize) {
    for (startCol in 0 until colSize) {
        for (endRow in startRow until rowSize) {
            for (endCol in startCol until colSize) {
                var currentPrefixSum = prefixSum[endRow][endCol]
                // 시작 점이 0행이면 뺄 구간이 없다.
                if (startRow > 0) currentPrefixSum -= prefixSum[startRow-1][endCol] 
                if (startCol > 0) currentPrefixSum -= prefixSum[endRow][startCol-1] // 열도 마찬가지
                if (startRow > 0 && startCol > 0)  currentPrefixSum += prefixSum[startRow-1][startCol-1]
                maxPartSum = currentPrefixSum.coerceAtLeast(maxPartSum)
            }
        }
    }
}

따라서 시간 복잡도는 시작점이 (0,0)일 때 끝 점이 (0,0)에서 (n-1, n-1)인 경우, 시작 점이 (0,1)일 때 끝 점이 (0,1)에서 (n-1, n-1)인 경우의 수와 같이 모든 부분 행렬의 경우의 수를 따져보면 알 수 있다.

시작 점이 (0,0)일 경우 n^2, (0,1)이면 n*(n-1), ... , (0, n-1)이면 n,

1행에서는 (1,0)이면 (n-1)*n, (1,1)이면 (n-1)*(n-1), ..., (1, n-1)이면 n-1이 된다.

이런 식으로 전부 구한다면 연산 횟수 = n*(1+...+n) + (n-1)*(1+...+n) + ... + (1+...+n) = (1+...+n)*(1+...+n)이며, n에 199를 넣어보면 대략 4억이다.

풀이 순서

1. (0,0)에서 각 점까지의 누적 합을 구한다.

2. 가능한 모든 시작 점과 끝 점을 확인하면서 모든 부분 행렬의 합을 구한다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (rowSize, colSize) = readLine().split(" ").map(String::toInt)
    val matrix = Array(rowSize) {
        val st = StringTokenizer(readLine())
        IntArray(colSize) { st.nextToken().toInt() }
    }
    val prefixSum: Array<IntArray> = calculatePrefixSum(matrix) // 0행0열에서부터의 누적합 기록
    var maxPartSum = matrix[0][0]
    
    // 부분행렬 [startRow][startCol] ~ [endRow][endCol]의 합
    for (startRow in 0 until rowSize) {
        for (startCol in 0 until colSize) {
            for (endRow in startRow until rowSize) {
                for (endCol in startCol until colSize) {
                    var currentPrefixSum = prefixSum[endRow][endCol]
                    if (startRow > 0) currentPrefixSum -= prefixSum[startRow-1][endCol]
                    if (startCol > 0) currentPrefixSum -= prefixSum[endRow][startCol-1]
                    if (startRow > 0 && startCol > 0)  currentPrefixSum += prefixSum[startRow-1][startCol-1]
                    maxPartSum = currentPrefixSum.coerceAtLeast(maxPartSum)
                }
            }
        }
    }

    print(maxPartSum)
}

// 누적합 배열 반환
fun calculatePrefixSum(matrix: Array<IntArray>): Array<IntArray> {
    val prefixSum = Array(matrix.size) { IntArray(matrix[0].size) }
    
    prefixSum[0][0] = matrix[0][0]
    // 0행 누적합
    for (i in 1 until prefixSum[0].size) {
        prefixSum[0][i] = prefixSum[0][i-1] + matrix[0][i]
    }
    // 0열 누적합
    for (i in 1 until prefixSum.size) {
        prefixSum[i][0] = prefixSum[i-1][0] + matrix[i][0]
    }

    // 1행1열에서 row행col열까지의 누적합
    for (row in 1 until prefixSum.size) {
        for (col in 1 until prefixSum[0].size) {
            prefixSum[row][col] =
                prefixSum[row][col-1] + prefixSum[row-1][col] + matrix[row][col] - prefixSum[row-1][col-1]
        }
    }
    
    return prefixSum
}

https://www.acmicpc.net/problem/2412

유형

HashSet + BFS (이분탐색을 사용해서 그래프를 따로 만들어서 풀 수도 있다고 한다.)

풀이

완전 탐색을 가장 먼저 떠올릴 수 있다, 시작점에서 모든 경우의 수를 다 가보는 것. 최소 횟수로 T에 도달하길 원하기 때문에 다른 경우의 수에서 이미 가본 곳을 다시 가보는 건 손해 -> 시간 초과가 난다. 따라서 이미 가본 곳은 다시 가지 않도록 한다. 이렇게 완전한 BFS 풀이가 됐다.

그래프와 visited는 어떻게?

그래프는 HashSet으로 나타낼 수 있다. x,y좌표로 Pair나 문자열을 구성해서 Set에 전부 저장한다. 그러면 현재 위치에서 -2 ~ +2를 한 새로운 좌표가 그래프에 포함되는지 바로 확인할 수 있다. 따라서, visited도 HashSet으로 나타낼 수 있다.

for (dx in -2..2) {
    val nextX = x + dx
    
    for (dy in -2..2) {
        val nextY = y + dy
        val coord = Pair(nextX, nextY)
        // holes: 그래프(홈)
        if (holes.contains(coord) && visited.contains(coord).not()) {
            visited.add(coord)
            q.offer(Triple(nextX, nextY, count + 1))
        }
    }
}

BFS도중 y좌표가 T인 걸 만나면 그동안 움직인 횟수를 출력, 그렇지 못했다면 마지막에 -1을 출력해준다..!

코드

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val (n, targetY) = readLine().split(" ").map(String::toInt)
    val holes = HashSet<Pair<Int, Int>>()
    val visited = HashSet<Pair<Int, Int>>()
    repeat(n) {
        val st = StringTokenizer(readLine())
        holes.add(Pair(st.nextToken().toInt(), st.nextToken().toInt()))
    }

    val q: Queue<Triple<Int, Int, Int>> = LinkedList()
    q.offer(Triple(0, 0, 0))

    while(q.isNotEmpty()) {
        val (x, y, count) = q.poll()

        if (y == targetY) {
            print(count)
            return
        }

        for (dx in -2..2) {
            val nextX = x + dx
            for (dy in -2..2) {
                val nextY = y + dy
                val coord = Pair(nextX, nextY)
                if (holes.contains(coord) && visited.contains(coord).not()) {
                    visited.add(coord)
                    q.offer(Triple(nextX, nextY, count + 1))
                }
            }
        }
    }

    print(-1)
}

https://www.acmicpc.net/problem/20437

유형

Map 자료구조

풀이

구하고자 하는 것

(1) 어떤 문자를 정확히 k개 포함하는 가장 짧은 문자열의 길이,

(2) 어떤 문자를 정확히 k개 포함하면서 그 문자가 앞,끝에 있는 문자열 중 가장 긴 것의 길이

(1)의 경우에도 가장 짧으려면 맨 앞, 뒤에 해당 문자가 있어야 한다. 따라서, 앞, 뒤에 어떤 문자가 있으면서 그 문자가 k개 있는 문자열의 가장 긴 것과 가장 짧은 것의 길이를 구해야 한다. 

아이디어

문자열의 앞에서부터 문자를 확인하면서 Map이나 배열에서 그 문자의 원소에 인덱스를 추가한다.

ex) "abca"

count['a'] = {0,3}, count['b'] = {1}, count['c'] = {2}

그러다가 어떤 문자의 인덱스 개수가 k개 이상이 되면, 그 문자를 발견할 때마다 그 인덱스에서 k번째 이전의 인덱스를 빼서 문자열의 길이를 계산한다. 그리고 그것을 가장 긴 문자열과 가장 짧은 문자열의 길이와 비교해서 갱신한다. 

for (i in str.indices) {
    val letter = str[i] - 'a'
    val idxList = idxListOfLetter[letter]
    idxList.add(i)

    // 해당 문자를 k개 이상 발견했을 때
    if (idxList.size >= k) {
        val length = i - idxList[idxList.size - k] + 1=
        shortestLength = length.coerceAtMost(shortestLength)=
        longestLength = length.coerceAtLeast(longestLength)
    }
}

전체 코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val t = readLine().toInt()
    val answer = StringBuilder()

    repeat(t) {
        val idxListOfLetter = Array(26) { mutableListOf<Int>() } // 각 문자가 발견된 인덱스를 저장하는 리스트
        val str = readLine()
        val k = readLine().toInt()
        var shortestLength = 10_001 // k개를 포함하는 가장 짧은 문자열 길이(3번)
        var longestLength = k - 1   // k개를 포함하고 앞,끝 문자가 해당 문자인 가장 긴 문자열 길이(4번)

        for (i in str.indices) {
            val letter = str[i] - 'a'
            val idxList = idxListOfLetter[letter]
            idxList.add(i)

            // 해당 문자를 k개 이상 발견했을 때
            if (idxList.size >= k) {
                val length = i - idxList[idxList.size - k] + 1
                // 가장 짧은 길이로 갱신 (3번)
                shortestLength = length.coerceAtMost(shortestLength)
                // 첫번째와 마지막 문자가 같은 문자열 중 가장 긴 걸로 갱신 (4번)
                longestLength = length.coerceAtLeast(longestLength)
            }
        }

        if (shortestLength == 10_001) { // 갱신이 안됐다 -> 어떤 문자가 k개인 문자열이 없다
            answer.append(-1).appendLine()
        } else {
            answer.append(shortestLength).append(' ').append(longestLength).appendLine()
        }
    }

    print(answer)
}

https://www.acmicpc.net/problem/2812

유형

그리디, 스택

풀이

포인트

• 필요한 만큼 삭제한다 -> 삭제했을 때 수의 길이는 항상 같다.
• 가장 크게 만든다 -> 앞에 나보다 작은 수가 있으면 삭제한다.

과정

1. 스택 선언
2. 입력 숫자를 앞에서 하나씩 확인 ->
   1. 필요한 만큼 다 삭제했다 -> 스택에 숫자 추가
   2. 삭제할 게 남아있다 ->
      1. 스택 위에 지금 숫자보다 큰 수가 있다 -> 삭제
      2. 위 과정을 스택이 비어있거나, 나보다 크거나 같은 수가 있거나, 삭제를 다 끝마칠 때까지 반복한다.
3. 수가 내림차순으로 잘 정렬돼 있으면, 위 과정에서 removeCount만큼 삭제가 일어나지 않을 수도 있으므로 남은 removeCount만큼 뒤에서 삭제한다.

Ex) 1253375에서 5개 삭제

- loop 0)

앞에 숫자가 없다. '1' 추가 (answer: 1)

- loop 1)

'1' < '2' => '1' 삭제, '2' 추가 (answer: 2)

- loop 2)

'2' < '5' =>  '2' 삭제, '5' 추가 (answer: 5)

- loop 3)

'5' > '3' =>  '3' 추가 (answer: 53)

- loop 4)

'3' == '3' =>  '3' 추가 (answer: 533)

- loop 5)

'3' < '7' =>  '3' 삭제 (answer: 53),

'3' < '7' => '3' 삭제, '7' 추가 (answer: 57)

- loop 6)

'7' > '5' => '5' 추가

- 예외 처리

삭제할 게 하나 남았으므로, 뒤에서 하나를 삭제한다.

코드

import java.io.BufferedReader
import java.io.InputStreamReader

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    var (_, removeCount) = readLine().split(" ").map(String::toInt)
    val strNumber = readLine()
    val answer = StringBuilder() // 스택으로 활용

    for (num in strNumber) {
        if (removeCount == 0) {
            answer.append(num)
            continue
        }

        // 감히 나보다 작은 녀석이 앞에 있어!? -> 삭제로 응징한다
        // 나보다 큰 행님 or 같은 애가 앞에 있다 -> ㅇㅋ 인정
        while (answer.isNotEmpty() && answer.last() < num && removeCount > 0) {
            answer.deleteAt(answer.lastIndex)
            removeCount--
        }
        answer.append(num)
    }

    // 숫자들이 이미 내림차순으로 잘 정렬돼있으면,
    // 남아있는 removeCount만큼 뒤에서부터 삭제한다
    while (removeCount-- > 0) {
        answer.deleteAt(answer.lastIndex)
    }
    print(answer)
}