[백준 문제풀기] #1406번 - 에디터 with Kotlin

아직 알고리즘 실력 멀었다..
알맞은 방법으로 전혀 접근하지 못했다ㅠ🤦🏻‍♀️ 

 

문제

🙆🏻‍♀️ How to solve

1차 접근

fun main() {
    val edit = readln().toList()
    var cursor = edit.size
    var result = edit.toMutableList()
    val count = readln().toInt()

    for (i in 1..count){
        val m = readln().replace(" ", "")
        if(m.contains("P")){
            val u = m.toList()
            result.add(cursor, u[1])
            cursor += 1

        }
        else if(m in "D"){
            if(cursor == result.size){
                continue
            }
            else{
                cursor += 1
            }
        }
        else if(m in "L"){
            if (cursor == 0){
                continue
            }
            else{
                cursor -= 1
            }
        }
        else{
            if (cursor == 0){
                continue
            }
            else{
                result.removeAt(cursor - 1)
                cursor -= 1
            }
        }

    }

    println(result.joinToString().replace(", ", ""))
}

받아오는 문자열을 배열에 넣고 mutablelist에 넣은 뒤, 케이스를 4개로 나누어 cursor를 기점으로 풀었는데, 시간초과가 났다.

정확한 시간초과 이유를 잘 모르겠지만 아마도 readln().replace(" ", "")에서 문자열에 비례하여 오랜 시간이 걸리고, 

result를 리스트로 관리할 때, 문자 하나를 추가하거나 삭제할 때 O(n)의 시간이 소요되어 O(n^2)가 소요되는게 아닐까 싶습니다. 

 

어떻게 푸는지 모르겠어서 구글링을 해본 결과 ListIterator이라는 요 아이가 정방향, 역방향으로도 순회가 가능하고 커서 기능도 존재한다고한다!

이 인터페이스를 사용하면 리스트의 요소를 앞뒤로 이동하면서 접근하고 수정할 수 있다.

 

 

*ListIterator의 주요 메서드

• hasNext(): 현재 위치에서 다음 요소가 있는지 여부를 확인합니다.
• next(): 현재 위치에서 다음 요소를 반환하고, 다음 위치로 이동합니다.
• hasPrevious(): 현재 위치에서 이전 요소가 있는지 여부를 확인합니다.
• previous(): 현재 위치에서 이전 요소를 반환하고, 이전 위치로 이동합니다.
• add(element: E): 현재 위치 바로 뒤에 요소를 삽입합니다.
• remove(): 현재 위치의 요소를 삭제합니다.
• set(element: E): 현재 위치의 요소를 주어진 요소로 대체합니다.

 

2차 접근

먼저 입력받은 문자열을 담을 수 있는 LinkedList를 생성해준다.

연결리스트를 사용하는 이유는

1. 데이터의 삽입과 삭제가 빈번한 경우: LinkedList는 요소의 삽입과 삭제가 배열과 비교하여 상대적으로 효율적이다.  요소를 삽입하거나 삭제할 때, 단순히 앞뒤 요소의 링크를 변경하면 되므로 O(1) 시간 복잡도로 수행할 수 있다.
2. 데이터의 크기가 동적으로 변경되는 경우: LinkedList는 요소의 크기가 동적으로 조절되는 상황에서 유용하다.
   배열은 초기에 고정된 크기를 가지고 있어 크기를 변경하려면 새 배열을 할당하고 데이터를 복사해야 하지만, LinkedList는 요소를 추가하거나 제거할 때 크기 조절이 자유롭다.
3. 순회가 빈번한 경우: LinkedList는 순회할 때 특히 처음부터 끝까지 순회할 때 유용하다.
   각 요소가 다음 요소를 가리키기 때문에 요소를 차례대로 순회하기 용이하다.

그 후  LinkedList list의 리스트 반복자(ListIterator)를 생성하고, 이를 count(커서) 변수에 저장한다.

 

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 count = list.listIterator(list.size)

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

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

 

이번 기회에 리스트의 삽입,삭제가 많은 경우 사용할 수 있는 좋은 메소드를 알게 되었다.