BOJ - 1406 에디터

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

1406번: 에디터

 

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다. 이 편집기가 지원하는 명령어는 다음과 같다.

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

 

해당 문제 같은 경우에는 스택 개념을 활용했습니다.

커서 위치를 기점으로 왼쪽, 오른쪽 스택을 나누어 계산했습니다.

    val leftStack = readLine().map { it.toString() }.toMutableList()
    val rightStack = mutableListOf<String>()
    val n = readLine().toInt()

 

첫 번째 옵션의 경우, 커서를 왼쪽으로 한 칸 옮기는 것이니 오른쪽 스택에 왼쪽 스택 리스트의 마지막 요소를 가져다 붙이고, 왼쪽 스택에서는 리스트의 마지막 요소를 제거합니다. removeAt을 활용하여 이동시킬 수 있습니다.

    "L" -> {
        if (leftStack.isNotEmpty()) {
            //커서를 기준으로 스택을 분리한다.
            rightStack.add(leftStack.removeAt(leftStack.lastIndex))
        }
    }

 

두 번째 옵션의 경우, 첫 번째와 반대로 왼쪽 스택에 오른쪽 스택 리스트의 마지막 요소를 가져다 붙이고, 오른쪽 스택에서는 리스트의 마지막 요소를 제거해 줍니다.

    "D" -> {
        if (rightStack.isNotEmpty()) {
            leftStack.add(rightStack.removeAt(rightStack.lastIndex))
        }
    }

 

B 옵션의 경우, 커서 왼쪽에 있는 문자를 삭제하므로, 왼쪽 스택의 마지막 요소를 제거해 주면 됩니다.

    "B" -> {
        if (leftStack.isNotEmpty()) {
            leftStack.removeAt(leftStack.lastIndex)
        }
    }

 

P $의 경우는 왼쪽에 잘라낸 Char를 새로 추가해 주면 되겠습니다.

else -> leftStack.add(cmd[2].toString())

 

전체 코드

fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
    val leftStack = readLine().map { it.toString() }.toMutableList()
    val rightStack = mutableListOf<String>() // 리스트로 스택 구현
    val n = readLine().toInt()

    repeat(n) {
        when (val cmd = readLine()) {
            "L" -> {
                if (leftStack.isNotEmpty()) {
                    //커서를 기준으로 스택을 분리한다.
                    rightStack.add(leftStack.removeAt(leftStack.lastIndex))
                }
            }
            "D" -> {
                if (rightStack.isNotEmpty()) {
                    leftStack.add(rightStack.removeAt(rightStack.lastIndex))
                }
            }
            "B" -> {
                if (leftStack.isNotEmpty()) {
                    leftStack.removeAt(leftStack.lastIndex)
                }
            }
            else -> leftStack.add(cmd[2].toString())
        }
    }
    val answer = StringBuilder()
    leftStack.forEach { answer.append(it) }
    for (i in rightStack.lastIndex downTo 0) { // 오른쪽 스택은 top부터 문자를 읽어야 한다
        answer.append(rightStack[i])
    }
    print(answer)
}