백준 1406번: 에디터 (Kotlin)

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

1406번: 에디터

 

풀이

자료구조에 관한 문제이다. 문자열을 어딘가에 저장해야 하는데, 커서의 개념이 존재하고 그걸 움직일 수도 있다. 커서에 방향이 있으므로 데이터에 순서가 있고, 추가/삭제가 쉬운 자료구조를 사용해야 한다. 따라서, 배열은 사용할 수 없고, 추가/삭제가 빠르고 데이터에 순서가 있는 연결 리스트를 생각해볼 수 있다. 

 

커서는 어떻게 구현할 수 있을까?

 

방법1) 연결 리스트

연결리스트를 응용하면 커서의 개념을 구현할 수 있다. 연결 리스트를 2개를 사용해서 커서의 왼쪽 리스트와 오른쪽 리스트의 개념으로 사용하면, 왼쪽 리스트의 끝과 오른쪽 리스트의 시작 지점 사이에 자연스럽게 커서가 생긴다. 그러면 왼쪽 리스트의 끝에 데이터를 추가/삭제할 수 있다.

ex) (왼쪽 리스트: a-b-c-d-x) - 커서 - (오른쪽 리스트: y) 

 

방법2) 스택

연결 리스트와 마찬가지로 왼쪽 스택과 오른쪽을 스택을 사용해서 구현할 수 있다. 양 스택의 꼭대기에 있는 데이터를 움직여서 커서를 움직이고, 왼쪽 스택의 pop/push로 커서 왼쪽에 데이터를 추가/삭제할 수 있다.

연결리스트와 차이점은 실제 문자열의 순서가 스택에 저장된 순서와 조금 다르다는 것이다. 문자열을 왼쪽에서 오른쪽으로 읽을 때, 왼쪽 스택의 바닥에서 꼭대기, 오른쪽 스택의 꼭대기에서 바닥 순서로 읽어야 한다.

 

방법3) listIterator

다른 사람들의 코드를 읽어보다가 문제에서 요구한 것과 완벽하게 동일한 자료구조가 자바에 존재한다는 걸 알게됐다. listIterator라는 녀석이다. Iterator 인터페이스를 상속한 것으로 Collection의 List에 사용할 수 있는데, 컬렉션의 요소에 접근, 추가, 삭제 등을 지원한다. Iterator는 정방향으로만 순회가 가능하지만 listIterator는 역방향으로도 순회가 가능하고 커서도 존재한다ㅋㅋ. 주의할 점은, 원래의 컬렉션 객체를 참조하기 때문에 Iterator에서 데이터를 추가/삭제하면 원래 객체에도 그대로 반영된다.

참고) http://www.tcpschool.com/java/java_collectionFramework_iterator 여기에 자세하게 설명되어 있다.

 

 

코드1 (연결 리스트)

import java.io.*
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    // 커서 왼쪽에 문자들 추가
    val leftList = LinkedList<String>().apply{ addAll(readLine().map{ it.toString() }) }
    val rightList = LinkedList <String>()
    val n = readLine().toInt()

    repeat(n){
        val cmd = readLine()

        when(cmd){
            "L" -> {
                if (leftList.isNotEmpty()){ // 커서 왼쪽에 문자가 있을 때
                    rightList.addFirst(leftList.pollLast())
                }
            }
            "D" -> {
                if (rightList.isNotEmpty()){ // 커서 오른쪽에 문자가 있을 때
                    leftList.addLast(rightList.pollFirst())
                }
            }
            "B" -> {
                if (leftList.isNotEmpty()){
                    leftList.removeLast() // 커서 왼쪽에 있는 문자 삭제
                }
            }
            else -> {
                leftList.add(cmd[2].toString()) // 커서 왼쪽에 문자 추가
            }
        }
    }

    val answer = StringBuilder()
    leftList.forEach { answer.append(it) } // 연결리스트는 순서대로 문자를 읽을 수 있다.
    rightList.forEach{ answer.append(it) }
    print(answer)
}

 

코드2 (스택: 리스트 사용)

import java.io.*
import java.util.*

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

    repeat(n){
        val cmd = readLine()

        when(cmd){
            "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)
}

 

코드3 (listIterator)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() = with(BufferedReader(InputStreamReader(System.`in`))){
    val str = readLine()
    val list = LinkedList<String>()
    str.forEach { 
        list.add(it.toString())
    }
    val iter = list.listIterator(list.size)

    val n = readLine().toInt()
    repeat(n){
        val cmd = readLine()

        when(cmd){
            "L" -> {
                if (iter.hasPrevious()){ // 커서 왼쪽에 데이터가 있으면
                    iter.previous()      // 그걸 리턴하고 커서를 반환할 데이터의 왼쪽으로 움직인다.
                }
            }
            "D" -> {
                if (iter.hasNext()){ // 커서 오른쪽에 데이터가 있으면
                    iter.next()      // 그걸 리턴하고 커서를 반환할 데이터의 오른쪽으로 움직인다.
                }
            }
            "B" -> {
                if (iter.hasPrevious()){
                    iter.previous()
                    iter.remove()   // 가장 최근에 리턴한 데이터를 삭제한다 -> 실제 리스트에도 반영된다
                }
            }
            else -> {
                iter.add(cmd[2].toString()) // 커서 위치에 데이터 추가 -> 리스트에 반영
            }
        }
    }

    val answer = StringBuilder()
    list.forEach {
        answer.append(it)
    }
    print(answer)
}