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

hansung's·2024년 3월 19일

문제 url:
도키도키 간식 드리미

문제:

🤔 문제 알아보기

기본적으로 해당 문제는 그림으로 설명을 잘해서, 문제만 읽어봐도 이해가 될 것이다.
그럼에도 간략히 설명을 하자면

tc가 5 4 1 3 2 순서로 있다고 가정하자,
만약 간식 받는 순번이 아니면 대기 공간으로 움직이며,
기다리는 줄 혹은 대기자가 현재 간식받는 순번과 일치하면, 간식 순번을 다음 순번으로 바꾸며 받은 자는 없어지는 그림이다.

1번째 간식 순반 | 5 4 1 3 2
-> 5, 4 는 순번이 아니기 때문에 대기 순번으로 이동
이런식으로 말이다.

음, 필자가 설명하는 것보다는 그림을 보고 이해하는게 훨씬 편하기 때문에 문제 설명은 여기까지 하겠다.

🐱‍👤 실제 코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] priority = new int[N];

        for(int i = 0; i < N; i++) {
            priority[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(checkToEat(priority));

    }

    static String checkToEat(int[] priority) {
        Stack<Integer> stack = new Stack<>();

        // 순번을 의미하는 변수
        int turn = 1;

        for(int i = 0; i < priority.length; i++) {

            // 만약 순번이 기존 줄 인원의 순번과 같으면 순번을 늘린다.
            if(turn == priority[i]) {
                turn++;
            }
            // 만약 순번이 대기 줄 인원의 순번과 같으면 순번을 늘린다.
            else if(!stack.empty() && stack.peek() == turn) {
                stack.pop();
                turn++;

                /*
                  * 반복을 줄이는 이유는, 예를 들어 6 4 3 1 2 5가 존재한다면
                  * 1, 2, 후 스택에 있는 3을 해야한다. 근데, 이때 반복이 끝나게 되는데,
                  * 그럴 경우 5를 구한 것이 아니므로 스택에서 찾은 반복은 반복횟수로 치지 않는 것이다.
                 */
                i--;
            } else {
                stack.push(priority[i]);
            }
        }

        /*
         * 스택에 남아있는 대기자들 순번 찾기
         */
        boolean result = true;

        for(int i = 0; i < stack.size(); i++) {
            int extra = stack.pop();

            if(turn == extra) {
                turn++;
            } else {
                result = false;
                break;
            }
        }
        return result ? "Nice" : "Sad";

    }
}

처음에는 문제가 그리 어렵지는 않다고 생각했다. 문제를 이해가 쉬웠기 때문이었는지...
하지만 이를 구현하고자 하니 너무 많은 경우의 수를 생각했고 이로인해 로직이 꼬이는 경우가 발생하였다.

결국... 풀지 못하고 타 블로그를 참조하여 문제를 풀어보았다.

👀 코드 풀이

		// 순번을 의미하는 변수
        int turn = 1;

        for(int i = 0; i < priority.length; i++) {

            // 만약 순번이 기존 줄 인원의 순번과 같으면 순번을 늘린다.
            if(turn == priority[i]) {
                turn++;
            }
            // 만약 순번이 대기 줄 인원의 순번과 같으면 순번을 늘린다.
            else if(!stack.empty() && stack.peek() == turn) {
                stack.pop();
                turn++;

                /*
                  * 반복을 줄이는 이유는, 예를 들어 6 4 3 1 2 5가 존재한다면
                  * 1, 2, 후 스택에 있는 3을 해야한다. 근데, 이때 반복이 끝나게 되는데,
                  * 그럴 경우 5를 구한 것이 아니므로 스택에서 찾은 반복은 반복횟수로 치지 않는 것이다.
                 */
                i--;
            } else {
                stack.push(priority[i]);
            }
        }

첫 번째로 checkToEat 메서드의 앞 부분인데, 해당 로직을 설명하자면

만약, 현재 간식 순번(turn)이 본 줄(prioirty)과 같으면
간식 순번을 1씩 증가한다.

그렇지 않고, 대기줄(stack)이 비어있지 않고 대기줄 최상단 값이 간식 순번(turn)과 같으면 대기줄 인원을 줄이며(pop) 간식 순번을 1씩 증가한다.

근데, 여기서 잠깐! i--를 해줘서 의도적으로 본 줄의 인원을 다음 인원으로 보도록 안하는데, 이 말이 무슨말이냐면

해당 그림은 tc가 5, 2, 1, 3, 4 인 경우이다.
이때 i가 3의 인덱스일 때 대기줄에 존재하는 2와 간식 순번을 비교하는 모습을 볼 수 있다.
원래라면 본 줄에 있는 3과 비교해야 하지만, 대기줄에 일치하는 순번이 있기 때문에 해당 인덱스는 넘어가게 된다. 그렇기 때문에 대기줄에서 비교한다고 놓친 본 줄의 인덱스도 다시 검토 받을 수 있도록 하기 위해 i--를 해주는 것이다.


        /*
         * 스택에 남아있는 대기자들 순번 찾기
         */
        boolean result = true;

        for(int i = 0; i < stack.size(); i++) {
            int extra = stack.pop();

            if(turn == extra) {
                turn++;
            } else {
                result = false;
                break;
            }
        }
        return result ? "Nice" : "Sad";