백준 18115 카드 놓기 Kotlin (덱)

문제 출처 : https://www.acmicpc.net/problem/18115

18115번: 카드 놓기

문제

수현이는 카드 기술을 연습하고 있다. 수현이의 손에 들린 카드를 하나씩 내려놓아 바닥에 쌓으려고 한다. 수현이가 쓸 수 있는 기술은 다음 3가지다.

1. 제일 위의 카드 1장을 바닥에 내려놓는다.
2. 위에서 두 번째 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.
3. 제일 밑에 있는 카드를 바닥에 내려놓는다. 카드가 2장 이상일 때만 쓸 수 있다.

수현이는 처음에 카드 N장을 들고 있다. 카드에는 1부터 N까지의 정수가 중복되지 않게 적혀 있다. 기술을 N번 사용하여 카드를 다 내려놓았을 때, 놓여 있는 카드들을 확인했더니 위에서부터 순서대로 1, 2, …, N이 적혀 있었다!

놀란 수현이는 처음에 카드가 어떻게 배치되어 있었는지 궁금해졌다. 처음 카드의 상태를 출력하여라.

입력

첫 번째 줄에는 N (1 ≤ N ≤ 106)이 주어진다.

두 번째 줄에는 길이가 N인 수열 A가 주어진다. Ai가 x이면, i번째로 카드를 내려놓을 때 x번 기술을 썼다는 뜻이다. Ai는 1, 2, 3 중 하나이며, An은 항상 1이다.

출력

초기 카드의 상태를 위에서부터 순서대로 출력하여라.

알고리즘 분류

• 자료 구조
• 덱

풀이

우선 1,2번 연산은 어떠한 리스트의 마지막 부분, 마지막에서 두 번째 부분을 출력한다고 하면 일반적인 배열 자료구조로 구현할 수 있다.

하지만 3번 연산에선 앞에 부분을 출력해야 하기 때문에 결국 앞쪽, 뒤쪽 양방향 연산이 필요하여 deque 자료 구조를 고려할 수 있다.

출력은 reverse를 하면 되기 때문에 역으로 할지, 정방향으로 할지는 크게 중요하지 않다.

2 3 3 2 1 입력을 보자.

정방향으로 연산한다면 2와 1 연산은 문제가 없다.

하지만 3 연산은 4를 바닥에 놓고 3을 또 바닥에 놓는다고 하면 이를 출력할 때 4보다 3이 먼저 출력되게 된다.

이를 해결하기 위해 주어진 입력을 역으로 연산해 보자. 카드 숫자도 5에서 1이 아니라 1에서 5 순서로 한다.

1 2 3 3 2

1연산으로 5가 맨 뒤에

{1}

2연산으로 2가 1 앞에

{2,1}

3연산으로 3이 맨 앞에

{3,2,1}

3연산으로 4가 맨 앞에

{4,3,2,1}

2 연산으로 5가 1 앞에

{4,3,2,5,1}

이를 역으로 출력하면

1,5,2,3,4

 

 

코드

import java.util.*

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()) {

    val n = getInt()
    val input = getIntList()

    val dq = ArrayDeque<Int>()
    var num = 1
    for(i in input.size-1 downTo 0){
        val order = input[i]
        when(order){
            1 ->{
                dq.addLast(num++)
            }
            2 ->{
                val temp = dq.pollLast()
                dq.addLast(num++)
                temp?.let{
                    dq.addLast(it)
                }
            }
            else ->{
                dq.addFirst(num++)
            }
        }
    }
    write("${dq.reversed().joinToString(" ")}")
    close()
}