[코틀린] 프로그래머스 lv3 : 표 편집 (카카오 기출문제 풀이)

문제 풀러 가기!

풀이

"U X": 현재 선택된 행에서 X칸 위에 있는 행을 선택합니다.
"D X": 현재 선택된 행에서 X칸 아래에 있는 행을 선택합니다.
"C" : 현재 선택된 행을 삭제한 후, 바로 아래 행을 선택합니다. 단, 삭제된 행이 가장 마지막 행인 경우 바로 윗 행을 선택합니다.
"Z" : 가장 최근에 삭제된 행을 원래대로 복구합니다. 단, 현재 선택된 행은 바뀌지 않습니다.

이 부분만 잘 읽으면 일단 정확성은 맞출 수 있는 문제입니다.
삭제할 때 stack에 따로 담아놓고, Z연산을 수행할 때 stack에 담긴 데이터를 pop하면 되는거죠.
그후 n의 길이의 "O"만으로 이루어진 문자열을 생성합니다.
그러고 나서 stack을 하나씩 pop하면서 pop된 데이터가 가르키는 인덱스에 X표시를 하시면 됩니다.

참고로 카카오는 정확성만 맞아도 부분점수가 인정되니 실제 시험에서는 효율성 맞추겠다고 아둥바둥 안하셔도 됩니다.
그럼에도 여기서 효율성을 챙기려면 약간의 생각이 필요합니다.

저는 처음에 LinkedList 를 활용하여 각각의 Tuple(행)을 담아주었습니다. (잦은 삭제 혹은 삽입에 유리한 자료구조죠.)
그러나 이론상 연결 리스트의 삭제 혹은 삽입에 사용되는 시간복잡도는 O(1)입니다.
다만 사실상 연결리스트는 처음부터 탐색을 하여 삽입 or 삭제 연산을 수행하기 때문에 O(n)의 복잡도가 수행됩니다.
결국엔 시간초과.

그러고 생각해 냈던 방법이 직접 O(1)으로 동작하는 이전 노드와 다음 노드를 의 정보를 담고있는 LinkedList를 직접 구현해주면 문제가 풀립니다.

@Java
int pre[] = new int[n]; // 이전 Tuple 주소
int next[] = new int[n]; // 다음 Tuple 주소

for (int i = 0 ; i < n ; i++) {
    pre[i] = i - 1;
    next[i] = i + 1;
}                                
next[n - 1] = -1; // 끝 행의 다음노드는 없으므로 -1

// 이후 다음 연산 명령에 따라 cursor의 위치, 데이터의 이전 노드, 다음 노드를 갱신해가면서 코드를 이어나가시면 됩니다.

이런식으로 구현해주면 총 O(n)의 시간복잡도로 해결하실 수 있습니다.

그러나 여기서 더 놀라운 사실을 알아냈습니다.
LinkedList 자체를 사용 안하고 테이블의 사이즈, cursor의 위치, stack에 쌓인 인덱스만 관리해주면 위의 로직보다 더 간결하게 구현할 수 있습니다.

@Kotlin
/** 참고로 코틀린의 when은 switch문과 같습니다. **/
when (c[0]) {
    "D" -> cursor += c[1].toInt() // 커서 밑으로 이동
    "U" -> cursor -= c[1].toInt() // 커서 위로 이동
    "C" -> { //삭제 명령 : Z연산을 대비해 Stack에 넣어두고 커서를 밑으로 이동시켜야함
        tableSize--
        deleted.add(cursor)
        cursor = if (cursor == tableSize) {cursor - 1} else cursor
    }
    "Z" -> { // Z 연산 : 삭제 행 복구, 현재 선택된 행은 바뀌지 않아야 됨
        tableSize++
        cursor = if(deleted.pop() <= cursor) cursor + 1 else cursor
    }
}

확실히 이전 노드, 다음 노드에 관한 신경을 써주지 않아도 되어 더 직관적으로 문제를 풀 수 있습니다.
물론 시간복잡도는 동일합니다.

Source Code

package Kakao_Internship_2021.표_편집

import java.util.*

class Solution {
    fun solution(n: Int, k: Int, cmd: Array<String>): String {
        var cursor = k
        val deleted = Stack<Int>()
        var tableSize = n

        for (i in 0 until cmd.size) {
            val c = cmd[i].split(" ")

            when (c[0]) {
                "D" -> cursor += c[1].toInt() // 커서 밑으로 이동
                "U" -> cursor -= c[1].toInt() // 커서 위로 이동
                "C" -> { //삭제 명령 : Z연산을 대비해 Stack에 넣어두고 커서를 밑으로 이동시켜야함
                    tableSize--
                    deleted.add(cursor)
                    cursor = if (cursor == tableSize) {cursor - 1} else cursor
                }
                "Z" -> { // Z 연산 : 삭제 행 복구, 현재 선택된 행은 바뀌지 않아야 됨
                    tableSize++
                    cursor = if(deleted.pop() <= cursor) cursor + 1 else cursor
                }
            }
        }
        val sb = StringBuilder()
        sb.append("O".repeat(tableSize))
        while (!deleted.isEmpty()) {
            sb.insert(deleted.pop(), 'X')
        }

        return sb.toString()
    }
}