[백준/BOJ] 1406번: 에디터

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

1406번: 에디터

문제

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.

이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽),

또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.

이 편집기가 지원하는 명령어는 다음과 같다.

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

해설

시간 초과로 인해 문제를 푸는데 애를 먹었다.

처음엔 LinkedList를 이용하여 각 명령어마다 그에 맞는 조건을 실행하였다.

하지만 LinkedList에선 요소의 위치를 배열처럼 한번에 접근하지 못해 add나 remove를 할 때 시간복잡도 O(n)이 걸려

시간 초과가 나게 된다.

 

이를 해결하기 위해 ListIterator<E>를 사용하였다.

ListIterator는 기존 LinkedList의 add나 remove처럼 처음부터 위치를 확인하는 것이 아닌, iterator의 위치에서 시작할 수 있다는 장점이 있다.

 

ListIterator를 선언한 후 처음 iterator의 위치는 0에 있다.

따라서 hasNext()를 통해 위치(idx)를 문장의 끝으로 옮겨준다.

while(iterator.hasNext()) iterator.next()

이후 문제에 나와있듯이 각 명령에 따른 조건을 실행하도록 하면 된다.

 소스 코드

import java.util.*

fun main() = with(System.`in`.bufferedReader()){
    val str = readLine()
    val list = LinkedList<Char>()

    for(i in str.indices) list.add(str[i])
    val iterator = list.listIterator()
    while(iterator.hasNext()) iterator.next()

    val n = readLine().toInt()
    repeat(n) {
        val input = readLine()
        val commend = input[0]
        if(commend == 'L') {
            if(iterator.hasPrevious()) iterator.previous()
        }
        else if(commend == 'D') {
            if(iterator.hasNext()) iterator.next()
        }
        else if(commend == 'B') {
            if(iterator.hasPrevious()) {
                iterator.previous()
                iterator.remove()
            }
        }
        else if(commend == 'P') {
            iterator.add(input[2])
        }
    }
    println(list.toCharArray())
}