[백준, 자료구조, Kotlin] P.1406 에디터

 

LinkedList를 활용해서 풀었습니다. 초기 코드는 시간 초과로 애를 먹었습니다.

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

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.`out`))

    val str = reader.readLine()
    val M = reader.readLine().toInt()

    val linkedList = LinkedList<Char>()
    val listIterator = linkedList.listIterator()

    while(listIterator.hasNext()) {
        listIterator.next()
    }

    str.forEach {
        linkedList.add(it)
    }
    var size = linkedList.size

    var index = str.length
    val result = StringBuffer()

    for(i in 0 until M) {
        val command = reader.readLine()
        when {
            command[0] == 'L' -> {
                if(index > 0) {
                    index--
                }
            }
            command[0] == 'D' -> {
                if(index < size) {
                    index++
                }
            }
            command[0] == 'B' -> {
                if(index > 0) {
                    linkedList.removeAt(index - 1)
//                    linkedList.listIterator(index).remove()
                    size--
                    index--
                }
            }
            command[0] == 'P' -> {
                linkedList.add(index, command[2])
//                linkedList.listIterator(index).add(command[2])
                size++
                index++
            }
        }
    }

    linkedList.forEach {
        writer.write(it.toString())
    }

    writer.flush()
    writer.close()
}

나름대로 성능 개선해보려고 size와 index를 두어서 매번 연산마다 list.size()나 인덱스를 찾기 위해 전체 탐색을 하지 않도록 구현했는데
이 방법도 부족했던것 같습니다.

결국 인터넷을 찾다 보니 linkedlist의 삽입/삭제 시 그 인덱스에 바로 접근하는 것이 아니라, head와 tail을 제외하곤 하나하나 살펴보며 찾아가서 (노드가 가리키는 주소로 몇번째로 찾아갔는지가 Index) 처리하기 때문에 완전히 효율적이라고 볼 수 없다는 내용을 확인했습니다.
Iterator는 아예 해당 노드를 가리키고 있다고 보면 됩니다.
(ex. next()를 하면 해당 노드의 next가 참조하는 노드를 가리키도록...)

자세한 내용은 조만간 정리해서 바로 밑에 링크 걸어두겠습니다.

이를 해결하기 위해 listIterator를 사용하는 것입니다. 기존 iterator와는 달리 양방향으로 커서를 이동시킬 수 있습니다.
다시 짠 코드입니다.

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.LinkedList

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))

    val str = reader.readLine()
    val M = reader.readLine().toInt()

    val linkedList = LinkedList<Char>()
    str.forEach {
        linkedList.add(it)
    }
    val listIterator = linkedList.listIterator()

    while (listIterator.hasNext()) {
        listIterator.next()
    }
    val result = StringBuffer()

    for (i in 0 until M) {
        val command = reader.readLine()
        when {
            command[0] == 'L' -> {
                if (listIterator.hasPrevious()) {
                    listIterator.previous()
                }
            }
            command[0] == 'D' -> {
                if (listIterator.hasNext()) {
                    listIterator.next()
                }
            }
            command[0] == 'B' -> {
                if (listIterator.hasPrevious()) {
                    listIterator.previous()
                    listIterator.remove()
                }
            }
            command[0] == 'P' -> {
                listIterator.add(command[2])
            }
        }
    }

    linkedList.forEach {
        result.append(it)
    }

    print(result.toString())
}

앞으로 list를 다룰때 insert, delete, update연산이 연속적으로 발생할때는 단순히 반복문에 index를 만져가며
다루는게 아니고 iterator를 적극적으로 활용해야겠다는 생각을 해봅니다.