[Kotlin] 백준 5430 : AC

문제 링크

5430번: AC

---

---

문제 해설

리스트나 덱(Deque)을 이용해서 풀 수 있는 문제다. 풀이 과정은 두 방법 모두 동일하다. 가장 먼저 입력에서 [x1,...,xn] 형태로 주어진 배열을 덱에 삽입하기 위해 입력값을 파싱해줘야 한다. slice() 메소드로 입력의 시작과 끝에 있는 대괄호를 제외한 문자열을 만들고 콤마(,)를 구분자로 하여 각 정수값을 덱에 삽입한 후 주어진 함수 연산을 시작한다.

 

문제의 함수에서는 뒤집기 연산이라는 것이 있는데 R이 들어왔을 때 정말로 뒤집어서 계산하면 안된다. R이 들어올 때마다 뒤집기를 수행하게 되면 배열의 크기\(\times\)뒤집기 횟수만큼 엄청난 부하가 가해지기 때문이다. 따라서, 문제의 해결 방법은 다음과 같다.

1. R 연산으로 배열이 뒤집혀 있는지를 확인할 boolean 변수를 선언
2. R 연산이 들어올 때마다 해당 boolean 변수를 이전 값의 반대값으로 변경
3. D 연산이 들어왔을 때
   • 배열이 비어있다면 'error'를 출력하고 다음 테스트케이스로 이동
   • 배열이 비어있지 않다면 배열이 뒤집힌 상태에 따라 맨 첫값이나 마지막 값을 제거
4. 함수 p의 모든 연산이 끝난 상태에서 배열이 뒤집힌 상태라고 체크되어 있으면 실제로 뒤집음
5. 최종 결과를 출력하고 다음 테스트케이스로 이동

Kotlin에서는 문자열 템플릿과 Collection 객체의 joinToString() 메소드를 이용하여 배열의 내용물을 손쉽게 제시된 조건의 형태로 출력할 수 있다.

---

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val bw = System.out.bufferedWriter()
    var p: String
    var arr: String
    var st: StringTokenizer
    loop@ for (i in 1..readLine().toInt()) {
        val deque = ArrayDeque<Int>()
        var isReversed = false	// 배열이 뒤집힌 상태인지 확인할 Boolean 변수
        p = readLine()
        readLine()
        st = StringTokenizer(readLine().also { arr = it }.slice(1 until arr.lastIndex))
        while (st.hasMoreTokens()) deque.add(st.nextToken(",").toInt())
        for (c in p) {
            when (c) {
                'R' -> isReversed = !isReversed
                'D' -> {
                    if (deque.isEmpty()) {
                        bw.write("error\n")
                        continue@loop
                    }
                    if (isReversed) deque.removeLast()
                    else deque.removeFirst()
                }
            }
        }
        if (isReversed) deque.reverse()
        bw.write("[${deque.joinToString(",")}]\n")
    }
    bw.close()
}

---

여담

덱 대신 리스트를 사용하여 문제를 풀 때는 ArrayList보단 LinkedList를 사용하는 것이 좋다. ArrayList는 시작 값을 제거할 때 뒤에 있는 요소들을 한 칸씩 당겨오기 때문에 시간이 오래 걸리지만 LinkedList는 시작과 끝 값을 제거할 때는 연결만 끊어주면 되기 때문에 시간상으로 이득을 본다.

위쪽부터 차례대로 LinkedList, ArrayList, Deque으로 제출한 결과