개발해요

https://leetcode.com/problems/rotate-image/

문제) n x n 배열의 시계방향 90도 회전

제한 조건) 입력 외의 2차원 배열은 사용하지 않는다

풀이)

(1) 행렬을 전치(행과 열 교환)시킨다 그리고 (2) 대칭되는 열들을 교환한다. 그러면 시계방향으로 90도 회전한 모습이 된다. 이렇게 풀 수 있는 이유는 입력 배열 안에서 회전시키려면 배열 내 원소들을 교환하는 방식으로 값을 바꿔야 하는데, 전치와 대칭열 교환 모두 그렇게 동작하기 때문이다.

코드

class Solution {
    fun rotate(matrix: Array<IntArray>): Unit {
        transpose(matrix)
        reflect(matrix)
    }
    
    // 행렬 전치(행 <-> 열)
    fun transpose(matrix: Array<IntArray>) {
        for (row in 0 until matrix.lastIndex) {
            for (col in row + 1 until matrix.size) {
                val temp = matrix[row][col]
                matrix[row][col] = matrix[col][row]
                matrix[col][row] = temp
            }
        }
    }
    
    // 대칭 col 간 스위칭
    fun reflect(matrix: Array<IntArray>) {
        for (col in 0 until matrix.size / 2) {
            for (row in matrix.indices) {
                val temp = matrix[row][col]
                matrix[row][col] = matrix[row][matrix.lastIndex - col]
                matrix[row][matrix.lastIndex - col] = temp
            }
        }
    }
}

https://leetcode.com/problems/wiggle-subsequence/

유형

DP or Greedy

과정

난이도가 medium 이었지만, 나 한정 hard였다. 신기하게도 어제는 아무리 문제를 뜯어보고 풀이를 맛봐도 알송달송했는데, 오늘은 이해가 된다.(쓰면서 알았다. 제대로 이해하진 못했다) 무의식에서 내 머리가 열심히 고생해준 것 같다ㅎ

처음 봤을 때 DP 같다는 생각이 들었다. 길이가 k인 배열에서 nums[k]를 지우냐, 지우지 않느냐에 따라서 가장 긴 wiggle sequence를 결정할 수 있을 것 같았다. 그래서 경우의 수를 따져보려고 했는데, 뭔가 복잡했다. 노트가 없었어서(^^;) 머리에서만 해결해려다 보니 그랬던 것 같다.

잘 모르겠어서 discussion을 찾아봤다. 리트 코드는 세계적으로 많은 유저들이 있어서 그런지, discussion이 활성화 돼있어서 참 좋다. 친절한 분들의 친절한 설명이 많다. 아무튼, 그런데 설명을 봐도 뭐가 뭔지 잘 모르겠다 싶었다. DP는 일반적으로 생각하는 방식과 달라서, 반대로 Greedy는 너무 직관적인 때가 많아서 어렵다는 생각이 든다. (대충 다 어렵다는 뜻)

풀이

다시 문제로 돌아와서, DP든 Greedy든 어떤 원소들은 지우는 게 항상 이득인 때가 있다. 이전 원소와 값이 같거나, positive/negative의 상태가 같을 때가 그렇다. 지우지 않으면 풀이를 종료해야 하기 때문이다. 그런데, 그런 원소들을 다 지우면 자연스럽게 Wiggle Sequence만 남는다. 값이 같거나 상태가 같은 원소를 다 지워버렸기 때문이다.

예를 들어 배열을 이전 항과의 상대적 상태로 표현했을 때 (상태: +,-,0), 000+++-+--++--- -> 0+-+-+-가 된다. 즉, 첫 원소를 제외하고 0(이전 항과 같음)은 모두 제거되고, 연속된 '+'나'-'는 하나만 남게 된다. 따라서, 이 작업만 해주면 자연스럽게 정답을 찾게 된다

그런데 조금 생각해보니까 뭔가 이상하다. 위의 예시 000+++-+--++---에서 숫자로 직접 해보면, 연속된 상태에서도 어떤 값을 지우느냐에 따라서 길이가 달라진다. 나는 이 부분을 이해하는 데 애를 먹었고, 사실 완벽하게 이해하지 못했다. 그래서 아이디어로 설명을 대신해보려고 한다. 배열 a,b,....,c,d (a<b, c>d)가 있을 때, (a,b)와 (c,d)는 b<c, b==c, b>c 상관 없이 항상 길이 3으로 연결할 수 있다.

코드

class Solution {
    fun wiggleMaxLength(nums: IntArray): Int {
        if (nums.size <= 1) {
            return nums.size
        }
        
        var answer = 1
        var prevDiff = 0
        
        for (i in 1 until nums.size) {
            val diff = nums[i-1] - nums[i]
            
            // 이전 두 수의 상태와 다른 경우
            // 등호를 통해 첫 원소와 연속해서, [5 5 5 3]처럼 처음에 같은 수들이 나오는 것도 처리할 수 있다
            if ((prevDiff >= 0 && diff < 0) || (prevDiff <= 0 && diff > 0)) {
                answer++
                prevDiff = diff
            }
        }
        
        return answer
    }
}

피드백

이해하기 어려운 부분이 DP와 관련이 있을 것 같다. DP 문제도 좀 꾸준히 풀어야지.

혼자 공부 특) 막히는 부분 해결하기 어려움ㅠㅠ

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