[Kotlin] 백준 12789 : 도키도키 간식드리미

문제 링크

12789번: 도키도키 간식드리미

---

문제 해설

스택을 사용하여 문제를 해결할 수 있다.

 

간식을 받기 위해서는 1번부터 순서대로 간식 받는곳으로 이동해야 한다. 그런데 줄이 뒤죽박죽 섞여있어서 왼쪽에 있는 1열의 공간을 이용하여 줄을 순서대로 간식을 받을 수 있게 해야한다. 이 1열의 공간을 일종의 스택으로 취급하여 문제를 해결하면 된다.

 

입력받은 학생 번호 순서대로 아래와 같이 간식 받기를 시도한다.

• 만약 현재 간식을 받아야 할 번호와 줄 맨 앞의 학생 번호가 일치하지 않는다면 대기 공간(스택)에 추가한다.
• 만약 현재 간식을 받아야 할 번호와 줄 맨 앞의 학생 번호가 일치한다면 해당 학생에게 간식을 지급하고 간식을 받아야 할 번호를 1 증가시킨다. 
  • 이후 대기 공간(스택)의 가장 앞에 있는 학생이 간식을 받아야 할 번호와 일치한다면 간식을 지급하고 간식을 받아야 할 번호를 1 증가시킨다.
  • 대기 공간(스택)의 가장 앞에 있는 학생이 간식을 받아야 할 번호와 일치하지 않을 때까지 반복한다.

 

마지막 학생까지 순회했을 때 스택에 학생이 남아있지 않으면 모든 학생이 간식을 받을 수 있는 것이라고 판단할 수 있다. 반대로 학생이 한 명이라도 남아있다면 간식을 받지 못하는 경우가 된다.

 

이미 간식을 받은 학생은 더 이상 필요하지 않은 정보이기 때문에 처음에 줄을 선 순서와 대기 공간을 나타낼 스택 외에는 따로 선언하지 않아도 된다.

 

아래 코에서는 덱을 사용했지만 풀이 과정은 동일하다.

Code

import java.util.StringTokenizer

fun main() = with(System.`in`.bufferedReader()) {
    val n = readLine().toInt()
    val students = StringTokenizer(readLine()).run { IntArray(n) { nextToken().toInt() } }
    val waiting = ArrayDeque<Int>()
    var current = 1
    for (student in students) {
        if (student == current) {
            current++
            while (waiting.isNotEmpty() && waiting.last() == current) {
                waiting.removeLast()
                current++
            }
        } else {
            waiting.addLast(student)
        }
    }
    println(if (waiting.isEmpty()) "Nice" else "Sad")
}