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

---

이번 문제는 간식 배부 문제인데, 제약 조건이 있다.
해당 조건을 파악하기 위해 문제에 걸려있는 그림을 그대로 가져왔다.

그림에서와 같이 무작위로 정수가 입력되며 이 정수가 순서이다.
또한, 순서에 맞지 않는 정수가 있다면 한 쪽 라인으로 빠지고 순서에 맞는 번호가 입력되면 도착지로 도달할 수 있다는 것이다.

설명이 꽤나 복잡할 수 있는데, 간단히 말하면 정수들이 입력되고 이를 순서대로 도달시킬 수 있는지를 묻는 문제이다.

즉, 다른 통로에 현재 맞는 순서가 아닌 정수를 두면서 진행했을 때 도착지에 순서에 맞지 않는 정수가 도달하면 문제의 인물인 승환이는 간식을 받지 못하게 되는 것이다.

예를 들어 현재 그림과 같이 5 4 1 3 2 가 입력되었다고 가정하면,
그림과 같은 순서로 1 2 3 4 5 순 도달이 가능하지만

만약 3 5 4 2 1 이 입력된 경우
1 2 가 도착지에 도달했을 경우 그 다음으로 올 수 있는 정수가 4이기 때문에 승환이는 간식을 받지 못하는 상황인 것이다.

사실 다른 것보다 이걸 해석하는데 시간이 많이 들었다.

처음에는 큐를 사용하려고 했지만 문제 자체의 요구가 스택 자료구조였기 때문에 스택을 사용하고자 마음을 먹었고, 스택을 두 개 활용해서 풀어야할지 고민했었다.

하지만 단순히 현재 순서를 나타내는 변수와 조건 분기만 잘 설정한다면 무리 없이 풀어낼 수 있는 문제이다.

start 라는 변수가 현재 도착지에 도달해야할 순서를 알려주는 변수일 때
조건 분기는 다음과 같다.

while (!stack.isEmpty() && stack.peek() == start) {
    stack.pop();
    start++;
}

앞서서 말했던 문제 풀이 방식을 적용한다면 스택에 정수를 순서대로 삽입하고 스택이 비어있지 않고 마지막 숫자가 start 변수와 같다면 해당 정수를 도착지에 도달했다고 파악하고 pop한다.

이후 순서대로 도달해야하기 때문에 start 변수를 하나 씩 더 해 나간다.

다만 이 연산은 역순으로 단발성으로 끝나는 게 아니라 연속되어야하기 때문에 while의 조건으로 입력해 주었다는 것에 유의해야한다.

결과적으로 스택에서 빠져나올 수 있는 정수가 start와 같지 않아진다면 도달할 수 없다는 의미이기 때문에 반복문이 종료되고 스택에는 값이 들어 있는 상태로 빠져나오게 된다.

이후 단순히

if (stack.isEmpty())     
    System.out.println("Nice");
else System.out.println("Sad");

스택이 비었는지 아닌지만 판단하면 끝난다.

전체 소스코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws java.io.IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Stack<Integer> stack = new Stack<>();
        int start = 1;

        while (n-- > 0) {
            int x = Integer.parseInt(st.nextToken());

            stack.push(x);

            while (!stack.isEmpty() && stack.peek() == start) {
                stack.pop();
                start++;
            }
        }

        if (stack.isEmpty())
            System.out.println("Nice");
        else System.out.println("Sad");
    }
}

---

이번 문제는 조건을 파악하기가 어려웠다.
아무리 생각해봐도 승환이가 어떡해야 간식을 받지 못하는 지 알기 어려웠는데, 아마 입출력 예시 중 실패에 대한 예시가 없어서 그랬던 것 같다.

입출력 예시가 상세하지 않으면 문제 파악이 어렵다.