[BOJ - 5430] [백준 - 5430] AC [Gold - 5] [Solved by Kotlin]

문제 설명

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

 

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

 

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

 

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

 

입출력 예

입력

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.
• 각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.
• 다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)
• 다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)
• 전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력    

 

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

 

예제 입력

4
RDD
4
[1,2,3,4]
DD
1
[42]
RRD
6
[1,1,2,3,5,8]
D
0
[]

예제 출력

[2,1]
error
[1,2,3,5,8]
error

코드

import java.io.BufferedWriter
import java.io.OutputStreamWriter
import java.util.*

val bw = BufferedWriter(OutputStreamWriter(System.out))
fun main() = with(System.`in`.bufferedReader()) {
	// TC의 갯수
    val t = readLine().toInt()
    repeat(t) {
    	// 명령어 
        val p = readLine()
        // 입력 배열의 크기
        val n = readLine().toInt()
        // 입력 배열 (앞뒤 [] 자르기)
        val arr = readLine().removeSuffix("]").removePrefix("[")
        // 입력배열을 문자열 -> 정수배열로
        val arr2 = if (arr.isEmpty()) intArrayOf() else arr.split(",").map { it.toInt() }.toIntArray()
        // 알고리즘에 사용할 덱 선언
        val deque: Deque<Int> = LinkedList<Int>()
        // 덱에 요소를 전부 집어넣고
        arr2.forEach {
            deque.add(it)
        }
        // 알고리즘 시작
        bw.write(printDeque(deque, p))
    }

    bw.flush()
    bw.close()
    close()
}
fun printDeque(deque: Deque<Int>, p: String): String {
	// R명렁어가 들어왔는지?
    var isReversed = true
    val sb = StringBuilder()
    // 명령어를 순회
    for (i in p) {
        when (i) {
        	// R이면 isReversed 값을 반전 (뒤집어진 상태 판단)
            'R' -> isReversed = !isReversed
            // D면 삭제
            'D' -> {
            	// 먼저 비어있는지 확인
                if (deque.isEmpty()) {
                	// 비어있다면 "error"를 리턴하며 종료
                    return "error\n"
                }
                // isReversed의 상태에 따라 덱의 앞에서 요소를 뺄 지, 뒤에서 뺼 지 판단
                when (isReversed) {
                    true -> deque.pollFirst()
                    false -> deque.pollLast()
                }
            }
        }
    }
    // 명령어 순회가 끝나면 최종 답안을 출력
    sb.append("[")
    // 덱이 비어있는지 확인하면서 답을 출력
    while(deque.isNotEmpty()) {
    	// isReversed에 따라 어디서 부터 출력할 지 결정
        when(isReversed) {
            true -> sb.append(deque.pollFirst())
            false -> sb.append(deque.pollLast())
        }
        if(deque.size != 0) sb.append(",")
    }
    sb.append("]\n")
    return sb.toString()
}

풀이

이 문제를 풀 때는 시행착오가 있었다 

처음엔 위 방식이 아니라 리스트로 add remove를 사용하여 해결하려 했었는데 add, remove 메소드의 시간복잡도가 커서 시간초과가 발생했었다.

그래서 문제의 키워드에 있는 덱을 사용하여 문제를 해결했다.

 

먼저 덱(Deque)이란 뭘까?

 

덱은 자료구조의 일종으로 큐(Queue)는 한 쪽에서만 데이터를 삽입하고 제거할 수 있는 자료구조라면 덱은 앞과 뒤 모두에서 데이터를 처리할 수 있는 자료구조이다.

 

 

이제 코드를 살펴보자

 

Main 함수절은 입력만 받도록 하였다.

순서대로 테스트케이스의 수- t, 명령어 문자열 - p, 입력배열의 크기 - n, 입력배열 - arr, arr2, 덱 - deque을 선언 및 초기화를 시켜주었다.

마지막에 bw.write(printDeque(deque, p))를 수행하여 정답을 출력하게 했다.

 

정답을 도출하는 알고리즘을 담은 함수인 printDeque(Deque, String)을 살펴보자

 

덱에 명령어를 적용시켜 알고리즘을 수행해야하니 Deque, String을 매개변수로 삼았다.

 

함수의 프로퍼티로 R명령어를 받았을 때 덱이 뒤집어졌는지 아닌 지를 판단하는 isReversed, 최종 문자열을 담을 StringBuilder인 sb를 선언하였다.

 

그 다음으로 명령어를 통해 덱을 조작하였다.

1. 명령어를 순회하면서 명령어가 R이라면 덱을 뒤집는다는 것이니 isReversed를 반전시켜주었다.

(여기서 직접 reversed() 같은 메소드로 뒤집지 않은 이유는 시간문제 때문이다. O(n)의 시간복잡도를 가져 시간초과가 발생할 수있다.)  (덱은 앞 뒤 모두에서 삽입,삭제가 가능하므로 isReversed라는 Bool값을 통해 앞에서 조작할 지, 뒤에서 조작할 지 결정할 수 있다.)

 

2. 명령어를 순회하면서 명령어가 D라면 덱의 맨 앞요소를 삭제하였다.

삭제하기전 먼저 덱이 비어있는지 확인하고 비어있다면 "error"를 반환시키며 종료시켰다.

비어있지 않으면 덱이 뒤집어져있는 상태를 확인해 뒤집어져있다면 맨 뒤의 값을 삭제하고, 뒤집어져있지 않다면 맨 앞의 값을 삭제하였다.

 

이런 1, 2의 과정을 모두 수행 한 후 덱 안에 남아있는 요소를 모두 출력한다.

 

while(deque.isNotEmpty())를 통해 덱 안의 모든 요소가 남아있지 않을 때 수행한다.

 

이 while절 안에서도 역시 isReversed의 상태를 판단하여 앞에서 부터 뽑아낼지, 뒤에서부터 뽑아낼지 를 결정하고 StringBuilder에 문자열을 넣어주고 최종 StringBuilder를 반환하여 출력시켜준다.

 

결과

안정적으로 통과한 것을 볼 수 있다.