개발해요

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

유형

정렬, 그리디 or 특정 알고리즘 X

풀이

풀이 순서

1. 일을 시작하는 시간(startTime)과 마지막 시간(endTime)으로 변환한다.

2. endTime이 가장 늦은(큰) 일부터 차례대로 최대한 늦게 일을 시작하도록 일의 시간을 확정 짓는다.

  => 따라서, 위 과정에 앞서 endTime 기준 내림차순으로 정렬한다.

3. 가장 빨리 시작하게 될 일의 startTime을 출력한다.

1. 일을 시작하는 시간(startTime)과 마지막 시간(endTime)으로 변환한다.

일을 시작하는 시간(startTime)과 마지막 시간(endTime)으로 변환한다.

ex) 걸리는 시간: 5, 끝내야 하는 시간 9 => endTime: 9 - 1 = 8, startTime: endTime - 5 + 1 = 4

이렇게 놓으면 endTime 바로 다음인 끝내야 하는 시간에 일이 끝나있게 된다.

data class Task(var start: Int, var end: Int)

repeat(taskSize) {
    val (duration, dueTime) = readLine().split(" ").map(String::toInt)
    taskList.add(Task(dueTime - duration, dueTime - 1))
}

2. endTime 값이 가장 큰 일부터 차례대로 최대한 늦게 일을 시작하도록 배치한다.

가장 늦게 일어나기 위해서 모든 일을 데드라인에 최대한 가깝게 배치하며, endTime 값이 가장 큰 task부터 스케줄을 확정한다. task(currentTask)를 스케줄할 때 직전에 배치한 task(nextTask)와 비교해서 타임 라인이 겹친다면, currentTask를 nextTask 바로 왼쪽으로 배치한다. 이렇게 하면 현재 상황에서 currentTask를 최대한 늦은 시간에 스케줄한 것이 된다.

ex) currentTask: task C, nextTask: task D

단, currentTask를 왼쪽으로 옮기는 과정에서 startTime < 0이 된다면, 제시간에 일을 끝낼 수 없다는 의미가 된다.

var prevTask = taskList[0]
for (i in 1 until taskSize) {
    val currentTask = taskList[i]

    // prevTask과 currentTask의 시간이 겹치는 부분이 있거나, 통째로 currentTask가 더 오른쪽에 있는 경우
    // -> currentTask를 겹치지 않게 왼쪽 옮긴다
    if (currentTask.end >= prevTask.start){ // currentTask가 prevTask에 걸쳐있는 경우
        val moveToLeftTime = currentTask.end - prevTask.start + 1
        currentTask.end -= moveToLeftTime
        currentTask.start -= moveToLeftTime
    }
    
    if (currentTask.start < 0) {
        print(-1)
        return
    }
    prevTask = currentTask
}

3. 가장 빨리 시작하게 될 일의 startTime을 출력한다.

위에서 수평선 기준 오른쪽에 있는 task부터 겹치지 않으면서 데드라인에 가깝게 배치하고 나면, 맨 왼쪽에 있는 task의 startTime이 일을 가장 늦게 시작할 수 있는 시간이 된다.

코드

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

// start: 일 시작 시간, end: 마지막 시간 -> end+1 시간에는 작업이 끝나있다 
data class Task(var start: Int, var end: Int)

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val taskSize = readLine().toInt()
    val taskList = mutableListOf<Task>()

    repeat(taskSize) {
        val (duration, dueTime) = readLine().split(" ").map(String::toInt)
        val task = Task(dueTime - duration, dueTime - 1)
        taskList.add(task)
    }

    // 가장 늦게 끝낼 일이 먼저 오도록 정렬
    taskList.sortByDescending { it.end } 

    // 비교 기준, 시간상 currentTask 바로 다음에 진행할 task
    var nextTask = taskList[0]
    
    for (i in 1 until taskSize) {
        val currentTask = taskList[i]

        // nextTask currentTask의 시간이 겹치는 부분이 있거나, 통째로 current가 더 오른쪽에 있으면
        // 겹치지 않게 current가 nextTask 직전에 끝나게 왼쪽으로 옮긴다
        if (currentTask.end >= nextTask.start){
            val moveToLeft = currentTask.end - nextTask.start + 1
            currentTask.end -= moveToLeft
            currentTask.start -= moveToLeft
        }

        // currentTask를 0초 이전에 시작해야 하면 -1 반환
        if (currentTask.start < 0) {
            print(-1)
            return
        }
        
        nextTask = currentTask // 비교 기준 갱신
    }

    print(taskList.last().start) // 가장 먼저 시작할 task의 시작 시간
}

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