[Kotlin/백준] 5430, AC (시간초과 해결)

[도입]

명령어 문자열와 배열을 주고 

각 명령어가 R 이면 뒤집고 D 면 앞 원소를 빼서 결과를 반환하는 문제

 

자세한 내용은 아래 링크를 참고

5430번: AC

 

[잘못된 풀이]

처음에 아래 방식처럼 reversed 와 drop 을 사용해서 계속해서 새로운 리스트를 생성하고, 심지어 reversed 는 내부 구현을 살펴보니 O(N) 인데 그걸 매번 불러서 시간초과가 났었다.

그것도 모르고 R 두 번 연속인 거 지우고 D 연속으로 나오면 일괄처리하는 등의 삽질을 했다.

아래는 그 초기 코드이다.

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

/**
 * 2022.03.03
 * 5430 AC
 * https://www.acmicpc.net/problem/5430
 *
 */
val br = BufferedReader(InputStreamReader(System.`in`))
fun main() {
    val loop = br.readLine().toInt()
    for (case in 0 until loop) {
        println(solution())
    }
}

private fun solution(): String {
    val orders = br.readLine()
    val n = br.readLine().toInt()
    var arr = br.readLine().drop(1).dropLast(1).split(",")


    if (n < orders.count { c -> c == 'D'}) return "error"

    orders.forEach { c ->
        if (c == 'R') {
            arr = arr.reversed()
        } else {
            arr = arr.drop(1)
        }
    }
    return StringBuilder().append("[").append(arr.joinToString(",") { it }).append("]").toString()
}

 

[정답 풀이 사고과정]

시간초과가 난다는 것은 병목이 일어나는 부분만 해결해주면 된다고 생각했고, 그 지점은 for 문이라고 생각했다.

그래서 바깥 반복문 안에서 일어나는 일이 어떻게 O(1) 이 되게 할지 고민했다.

그리고 방향을 뒤집고 앞쪽을 삭제하는 명령어밖에 없으므로 방향만 기억하고 양쪽 끝 중 하나를 제거하면 되겠다는 생각에 닿았다. 

아래는 해당 아이디어를 반영한 코드이다.

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

/**
 * 2022.03.03
 * 5430 AC
 * https://www.acmicpc.net/problem/5430
 * R 을 만날 때마다 뒤집는다면 시간초과가난다.
 * 명령어가 최대 10만이고 문자열 길이도 최대 10만이면 가볍게 1억이 훌쩍 넘어가기 때문이다.
 * 그래서 직접 뒤집지 않고 방향만 기록하고, 기록된 방향에 따라 앞뒤로 삭제하는 게 문제해결의 핵심이다.
 */
val br = BufferedReader(InputStreamReader(System.`in`))
fun main() {
    val loop = br.readLine().toInt()
    for (case in 0 until loop) {
        println(solution())
    }
}

private fun solution(): String {
    val orders = br.readLine()
    val n = br.readLine().toInt()
    val listString = br.readLine().drop(1).dropLast(1).split(",").toMutableList() // MutableList 로 바꿔야 삭제 가능
    val arr = LinkedList<String>()
    arr.addAll(listString)


    if (n < orders.count { c -> c == 'D' }) return "error"

    var direction = true // 정방향 역방향
    for (i in orders.indices) { // 이 반복문에서 일어나는 일이 시간복잡도 O(1) 이어야 시간초과가 나지 않는다.
        if (orders[i] == 'R') {
            direction = !direction // 방향만 바꿔준다.
        } else {
            if (direction) {
                arr.removeFirst()
            } else {
                arr.removeLast()
            }
        }
    }

    if (!direction) arr.reverse() // 마지막에만 방향이 바뀌어있다면 바꿔준다.

    return "[" + arr.joinToString(",") { it } + "]"
}

[반성]

굉장히 단순한 문제인 줄 알았는데 괜히 이상한 부분에서 삽질했다.

간단한 문제를 봐도 항상 시간복잡도를 생각하며 어떻게 효율적인 코딩을 할 수 있을지 고민해야겠다.

아 그리고 중간에 단순한 실수를 했는데 StringBuilder 를 마치 리스트로 생각해서 두 자리수를 고민하지 않아 오답을 불러일으켰는데, 정확하게 생각해야겠다.