[백준][BOJ 12789] - 도키도키 간식드리미

문제

https://www.acmicpc.net/problem/12789

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

 

 

문제 접근

• 따로 뺄 수 있는 대기열이 존재하고 이 대기열의 구조는 먼저 들어간 사람이 가장 마지막으로 나오는 구조이다. 따라서 LIFO의 특성을 가진 stack을 사용하여 이 대기열을 만들 수 있다.
• 일반적인 줄의 경우 대기열이기 때문에 queue로 모델링할 수 있다.
• 문제를 해결하는데 있어 가장 핵심적인 로직은 현재 간식을 받을 번호표와 지금 줄의 맨 앞에 서 있는 사람의 번호표가 서로 일치하지 않을 때 과연 어떻게 처리를 해야 할 것인가이다.
• 다음의 입력 예제를 생각해보도록 하자.

5
5 4 1 3 2

• 맨 처음 간식을 받아야 하는 대기표는 1번이다. 하지만 줄의 맨 앞사람의 번호는 5이다.
• 번호가 맞지 않으므로 먼저 따로 뺀 대기열의 맨 앞사람을 확인하여 간식을 받아야 하는 대기표의 번호와 동일한지 확인한다. 만약 따로 뺀 대기열에 아무도 존재하지 않는다면 맨 앞사람을 대기열로 빼낸다.
• 다음 사람은 4이다. 따로 뺀 대기열(이후 stack 이라고 하겠다.)의 맨 앞사람의 번호를 확인한다. 5이므로 4번 역시 stack에 넣는다.
• 그다음은 1번이다. 간식을 받아야 하는 대기표와 동일한 번호이므로 간식을 받고 빠지게 된다. 이후 간식을 받아야 하는 대기표는 2번이 된다.
• 그 다음 3번이 줄의 맨 앞으로 온다. 2번이 아니고, stack의 맨 앞사람도 4번이므로 stack에 집어넣게 된다.
• 이후 2번이 줄의 맨 앞으로 오고, 간식을 받을 대상자이기 때문에 그대로 빠지게 된다.
• 이후로는 stack에서 차례로 간식을 받고 빠질 수 있으므로 모든 사람이 간식을 받을 수 있게 된다.

 

여기까지는 순조롭다. 다음 예제를 살펴보자.

5
4 5 1 3 2

• 두 번째 5에서 문제가 발생한다. stack에 넣을 시 나중에 들어간 번호가 먼저 나오게 된다. 그런데 간식표는 항상 순서대로 올라가기 때문에 4번을 빼낼 방법이 존재하지 않게 된다.
• 따라서 모든 사람이 간식을 다 받을 수 없게 된다. 이 예제를 통해 다음과 같은 사실을 알 수 있다.
  • 대기열의 가장 앞 번호가 stack의 가장 앞 번호보다 크고 stack의 가장 앞 번호가 간식을 받아야 하는 번호가 아닌 경우 모든 사람이 간식을 받는 경우는 존재하지 않는다.
  • 대기열의 가장 앞 번호가 stack의 가장 앞 번호보다 작다면, 순서대로 받을 수 있는 방법이 존재한다.
• 이 규칙을 통해 문제를 해결할 수 있다.

 

 

정답 코드

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

public class Main {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());

    Deque<Integer> queue = new ArrayDeque<>();
    Deque<Integer> stack = new ArrayDeque<>();
    int currentNumber = 1;

    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++){
      queue.addLast(Integer.parseInt(st.nextToken()));
    }

    while(currentNumber <= N){

      // if queue is empty -> if not match current number
      if (!queue.isEmpty()){
        if (queue.peekFirst() != currentNumber){

          if (stack.isEmpty()){
            stack.addLast(queue.pollFirst());
          } else{
            if (queue.peekFirst() < stack.peekLast()){
              stack.addLast(queue.pollFirst());
            } else {
              if (stack.peekLast() == currentNumber){
                stack.pollLast();
                currentNumber++;
              } else{
                System.out.println("Sad");
                return;
              }
            }
          }
        } else{
          queue.pollFirst();
          currentNumber++;
        }
      } else{
        if (stack.peekLast() == currentNumber){
          stack.pollLast();
          currentNumber++;
        } else{
          System.out.println("Sad");
          return;
        }
      }
    }

    System.out.println("Nice");
  }
}

• 줄이 비어있지 않은 경우에 뒷 부분에 매칭되는 번호가 존재할 수 있으므로 위에서 살핀 조건들을 통해 스택에 넣을 수 있다면 스택에 넣고 불가능한 경우, Sad를 출력한다.
• 줄이 비어있다면 stack에서 빼내어 확인하도록 하면 된다.