(Kotlin) 프로그래머스 - 표 편집 [2021 카카오 채용연계형 인턴십]

https://programmers.co.kr/learn/courses/30/lessons/81303

코딩테스트 연습 - 표 편집

 

풀이1

처음에 스택을 활용한 커서 구현 방법과 배열에 삭제 여부를 표시하는 방식을 사용해서 정확도는 통과할 수 있었지만, 효율성 테스트에서 문제가 있었다. 두 가지 방법 모두 삭제된 행을 복구할 때 O(N)이 소요됨에 따라 명령어 * 전체 행 = 약 2000억 번의 연산이 필요하기 때문이다. 커서를 움직이는 숫자의 합은 100만 이하라고 주어졌기 때문에, 복구하는데 걸리는 시간을 줄여야 효율성 테스트를 통과할 수 있다. 그리고 연결 리스트를 사용하면 O(1)으로 해결할 수 있다.

 

연결 리스트

 

그림과 같이 연결리스트를 사용해서 삭제한 행을 스택에 저장하면, 삭제 과정이 연결리스트의 삽입과 같아진다.

그리고 항상 최근에 삭제된 행부터 복구하기 때문에, 삭제가 된 이후의 커서 이동이나 삭제는 신경쓰지 않고 이전 상태 그대로 복구할 수 있다. 단, 삭제하거나 복구할 때 양 끝의 행인지만 주의하면 된다!

 

풀이 2

삭제/복구 동작을 유심히 살펴보면 재밌는 사실을 발견할 수 있는데, 행을 삭제하더라도 cursor의 인덱스는 같다는 것이다.

 

ex)

0-1-2-3-4, cursor: 3, size: 5 

----삭제----

0-1-2-4, cursor: 3(4를 가리킴), size: 4, stack: 3

 

즉, cursor의 인덱스와 행의 개수만으로 차트를 표현할 수 있다. 단, 마지막 행을 삭제했을 때는 cursor -= 1을 해주어야 하는데, 이것도 실제 삭제 동작과 같다.

 

ex)

0-1-2-3-4, cursor: 4, size: 5

----삭제----

0-1-2-3, cursor: 4 - 1 = 3, size: 5, stack: 4

 

복구할 때는 행의 개수를 다시 증가시키고, 만약 현재 cursor의 인덱스가 복구하려는 행의 인덱스보다 크거나 같으면 cursor += 1을 해준다. 왜냐면 아래로 밀어야 하기 때문이다.

 

ex)

0-1-2-4, cursor: 3 (4를 가리킴), size: 4, stack: 3

----복구----

0-1-2-3-4, cursor: 3 + 1 = 4, size: 5

 

 

이런 풀이도 있다 정도로 알면 좋을 것 같습니다.

코드2를 참고해주세요!

 

코드1 (연결 리스트 사용)

import java.util.*

// 행 넘버, 위에 행, 아래 행, 삭제 여부
data class Row(val number: Int, var prev: Row? = null, var next: Row? = null, var state: Char = 'O')

class Solution {
    fun solution(n: Int, k: Int, cmd: Array<String>): String {
        val rowArray = Array<Row>(n) { i -> Row(i) }
        for (i in 0 until n-1) { // 앞으로 연결
            rowArray[i].next = rowArray[i+1]
        }
        for (i in 1 until n){    // 뒤로 연결
            rowArray[i].prev = rowArray[i-1]
        }

        var cursor = rowArray[k]
        val removeStack = Stack<Row>()

        cmd.forEach {
            when (it[0]) {
                'U' -> { 
                    val prevStep = it.split(" ")[1].toInt()
                    repeat(prevStep) {
                        cursor = cursor.prev!!
                    }
                }

                'D' -> {
                    val nextStep = it.split(" ")[1].toInt()
                    repeat(nextStep) {
                        cursor = cursor.next!!
                    }
                }

                'C' -> {
                    val removeRow = cursor
                    val prevRow = cursor.prev
                    val nextRow = cursor.next
                    removeStack.push(removeRow)
                    removeRow.state = 'X' // 삭제 표시

                    if (nextRow == null) { // 삭제될 행이 마지막 행인 경우
                        cursor = prevRow!!
                        prevRow.next = null
                    }else{
                        cursor = nextRow
                        nextRow.prev = prevRow

                        // 첫번째 행을 삭제하는 경우를 고려하지 않으면 NullPointerexception 발생
                        if (prevRow != null) prevRow.next = nextRow
                    }
                }

                else -> {
                    val removedRow = removeStack.pop()
                    val prevRow = removedRow.prev
                    val nextRow = removedRow.next
                    removedRow.state = 'O'

                    if (nextRow == null){ // 마지막 행이었던 경우
                        prevRow!!.next = removedRow
                    }else{
                        nextRow.prev = removedRow

                        if (prevRow != null) prevRow.next = removedRow
                    }
                }
            }
        }

        // 배열에 저장하지 않고 head, tail을 사용해서
        // 스택에 남아있는 행들을 다시 삽입한 후
        // head부터 순서대로 출력할 수도 있습니다.
        val answer = StringBuilder()
        rowArray.forEach {
            answer.append(it.state)
        }

        return answer.toString()
    }
}

 

코드2 (cursor랑 size로 차트 표현)

import java.util.*

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

        cmd.forEach {
            when (it[0]) {
                'U' -> {
                    val step = it.split(" ")[1].toInt()
                    cursor -= step
                }
                'D' -> {
                    val step = it.split(" ")[1].toInt()
                    cursor += step
                }
                'C' -> {
                    removeStack.push(cursor)
                    size -= 1
                    if (cursor == size) cursor--
                }
                else -> {
                    val comebackRow = removeStack.pop()
                    size += 1
                    if (comebackRow <= cursor) cursor++
                }
            }
        }

        val answer = StringBuilder()
        for (i in 0 until size) answer.append('O') // 살아있는 행 먼저 표시
        
        while (removeStack.isNotEmpty()) {
            val removedRow = removeStack.pop()     // 연결리스트의 삽입과 같다
            answer.insert(removedRow, 'X')
        }

        return answer.toString()
    }
}