백준 5397 키로거 Kotlin

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

백준 5397 키로거 문제 해결 및 배운 점

해결 코드

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val case = readLine().toInt()
    val answer = StringBuilder()

    for(i in 1..case){
        val input = readLine()
        val pw = LinkedList<Char>()
        var cursor = 0

        for(c in input){
            when(c){
                '<' -> cursor = if(cursor > 0) cursor - 1 else 0
                '>' -> cursor = if(cursor < pw.size) cursor + 1 else pw.size
                '-' -> {
                    if(pw.isNotEmpty() && cursor > 0)
                        pw.removeAt(--cursor)
                }
                else -> {
                    pw.add(cursor++, c)
                }
            }
        }
        for(c in pw){
            answer.append(c)
        }
        answer.append("\n")
    }
    print(answer.toString())
}

풀이)
1. 풀이할 패스워드를 Char 리스트로 선언
2. Int형 cursor 변수를 선언하여 pw의 cursor 자리에 다음 문자가 들어가도록 함
3. input String을 앞에서부터 문자 하나씩 해석.
문자가 '<'일 경우 cursor를 앞으로 한 칸(cursor 위치 1 이상 아니면 0)
문자가 '>'일 경우 cursor를 뒤로 한 칸(cursor 위치 pw 크기보다 작지 않으면 size)
문자가 '-'일 경우 해당 위치의 문자를 제거(cursor는 다음 문자가 들어갈 자리이므로 현재 위치를 제거하기 위해 --cursor)
그 외 문자는 리스트의 cursor 위치에 add
패스워드를 해석한 뒤, 효율을 위해 StringBuilder로 결과를 연결하여 출력

배운 점)
처음에 pw변수를 mutableListOf를 이용해 MutableList 타입으로 선언하였으나, input 문자가 1~1,000,000이므로 add / remove에 오랜 시간이 걸려 시간 초과.

1,000,000 길이의 문자열을 분석하고 리스트에 추가하려는 경우 굉장히 자주 MutableList가 재할당될 수 있을 것 같아 이를 원소 추가/제거에 유리한 LinkedList로 바꿈

지금처럼 리스트에 원소를 많이 추가 / 제거하는 경우 MutableList가 아닌 LinkedList가 큰 도움이 될 수 있음.

+) 해당 문제처럼 커서를 사용해 위치를 다루는 경우, Stack 2개를 사용하여 해결할 수도 있음