개발해요

https://leetcode.com/problems/spiral-matrix/

유형

구현

풀이

달팽이 모양으로 행렬의 포인터를 이동시켜보는 문제였다.

1. 행렬에 포인터를 두고, 오른쪽, 아래, 왼쪽, 위, 오른쪽, 아래,... 의 순서로 방향을 바꿀 수 있도록 방향 배열을 설정한다.

var row = 0; var col = 0
val dRow = intArrayOf(0, 1, 0, -1)
val dCol = intArrayOf(1, 0, -1, 0)
var dir = 0

2. 방향 변경 조건 설정

현재 위치에 있는 숫자를 정답에 추가하고 우선 현재 방향대로 한 칸 이동한다. 이 때, 아래 그림과 같이 이동한 위치가 행렬의 범위를 벗어나거나 이전에 확인했던 곳이라면 이동하기 전의 위치에서 방향을 바꿔서 다시 이동한다. 

var nextRow = row + dRow[dir]
var nextCol = col + dCol[dir]
// 현재 방향대로 이동했을 때 행렬을 벗어나거나 이전에 추가했던 위치면 방향을 변경
// 101: 확인한 곳
if (nextRow !in matrix.indices || nextCol !in matrix[0].indices || matrix[nextRow][nextCol] == 101) {
    dir = (dir + 1) % 4
}
row = row + dRow[dir]
col = col + dCol[dir]

3.  2번의 과정을 반복한다. 단, 무한 루프에 빠지지 않도록 숫자를 모두 추가했으면 반복문을 빠져나온다.

answer.add(matrix[row][col])
matrix[row][col] = 101 // 해당 위치의 숫자를 추가했다는 표시
// 다 추가했으면 스탑
if (++addCount >= addLimit) {
    break
}

전체 코드

class Solution {
    fun spiralOrder(matrix: Array<IntArray>): List<Int> {
        // right, down, left, up
        val dRow = intArrayOf(0, 1, 0, -1)
        val dCol = intArrayOf(1, 0, -1, 0)
        var dir = 0
        var row = 0; var col = 0 // 현재 좌표
        var addCount = 0         // 추가한 숫자 개수
        val addLimit = matrix.size * matrix[0].size // 최종 추가할 개수
        val answer = mutableListOf<Int>()
        
        while (true) {
            answer.add(matrix[row][col])
            matrix[row][col] = 101 // 해당 위치의 숫자를 추가했다는 표시
            // 다 추가했으면 스탑
            if (++addCount >= addLimit) {
                break
            }
            
            var nextRow = row + dRow[dir]
            var nextCol = col + dCol[dir]
            // 현재 방향대로 이동했을 때 행렬을 벗어나거나 이전에 추가했던 위치면 방향을 변경
            if (nextRow !in matrix.indices || nextCol !in matrix[0].indices || matrix[nextRow][nextCol] == 101) {
                dir = (dir + 1) % 4
            }
            row = row + dRow[dir]
            col = col + dCol[dir]
        }
        
        return answer
    }
}

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)
}