문제 출처

단계별로 풀어보기 > 스택 큐 덱 > 도키도키 간식드리미
https://www.acmicpc.net/problem/12789

문제 설명

각각의 번호표를 가진 사람들이 간식으로 받으로 올 때, 자신의 차례가 아닌 경우 대기 줄로들어가게 된다. 이 때, 대기줄은 가장 마지막에 들어온 사람이 가장 처음으로 나갈 수 있다(자신의 번호 차례에만).
해당 과정을 검증할 수 있는 프로그램을 구현하라.

접근 방법

처음 대기줄에서 자신의 번호인 경우와 아닌 경우를 따진다.
번호가 맞는 경우
현재 대기 스택에 들어간 인원들 중 다음 차례인 인원들을 계속 간식을 준다.
아닌 경우
대기 스택에 push한다.

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

public class 도키도키_간식드리미 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        Stack<Integer> stack = new Stack<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int count = 1;

        for (int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());

            if (num == count) {
                count++;
                // 간식 줄 수 있으면 바로 줌
                while (!stack.isEmpty() && stack.peek() == count) {
                    stack.pop();
                    count++;
                }
            } else {
                stack.push(num);
            }
        }

        if (stack.isEmpty()) {
            bw.write("Nice");
        } else {
            bw.write("Sad");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

Review

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

public class 도키도키_간식드리미_review {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        Stack<Integer> stack = new Stack<>();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int count = 1;
        for(int i = 0; i<N; i++){
            int k = Integer.parseInt(st.nextToken());
            if(k == count){
                count++;
                while(!stack.isEmpty() && stack.peek() == count){
                    stack.pop();
                    count++;
                }
            }else{
                stack.push(k);
            }
        }
        bw.write(stack.isEmpty()?"Nice":"Sad");
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

처음문제를 풀 때는,
접근으로 자신의 차례가 아닌 경우 대기 스택에서 peek하여 peek한 대상이 해당 번호인 경우 pop하고, 대기 줄에 있는 인원은 그 stack 안으로 넣는 방식을 택했다. 하지만 이는 대기 줄에 있는 인원이 쓸 때 없이 push되어 stack 안에 있는 인원을 방해하는 로직의 문제가 있었다.

문제푼 흔적

Review