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

도키도키 간식드리미

문제

---

문제 설명

일단 문제 길이가 굉장히 길어서 어려워보이지만 그냥 간단하게 생각하면 줄이 있고 그 줄을 다른 공간에 집어넣으면서 과연 순서대로 간식을 받을 수 있는지 푸는 문제이다.

문제상에서 주어진 대기열은줄을 서 있는 대기열 과 추가 대기열 이 있다.

줄을 서 있는 대기열은 입력된 순서대로 나오기 때문에 Queue 를 사용하고, 추가 대기열의 순서는 들어간 역순으로 나오기 때문에 Stack을 사용했다.

기존에 입력을 받았던 Queue로 Stack 에 넣었다가 빼면서 생각해주면 되는데 아래 주요 로직 코드를 먼저 보고 설명을 하겠다.

int index = 1;

while (!queue.isEmpty()) {
	if (queue.peek() == index) {
		queue.poll();
		index++;
	} else if (!stack.isEmpty() && stack.peek() == index) {
		stack.pop();
		index++;
	} else {
		stack.push(queue.poll());
	}
}

일단 맨 처음 대기열이 비어지지 않을 때까지 반복한다.

만약에 기존의 대기열의 첫 사람, 즉 peek을 한 사람이 현재의 index와 같다면 해당 사람을 빼내고 index 를 늘린다.

그렇지 않고 추가 대기열이 비어있지 않고 가장 마지막에 들어간 사람이 index 와 같다면 해당 사람을 빼내고 index 를 늘린다.

다 그렇지 않다면 순서가 올바르지 않은것이기 때문에 추가대기열에 기존대기열의 사람을 추가해준다.

이런식으로 진행이 된 후에 마지막에 추가 대기열에 있는 사람을 체크한다.

while (!stack.isEmpty()) {
	if (stack.peek() == index) {
		stack.pop();
		index++;
	} else {
		System.out.println("Sad");
		return;
	}
}

추가 대기열인 Stack이 비지 않을 때까지 Stack의 가장 위 항목을 꺼내서 index와 같다면 해당 사람을 빼고 index를 추가하는 기존 방식을 그대로 사용하고 만약 다르다면 불가능한것이기 때문에 Sad 를 출력하고 함수를 종료하게 된다.

이렇게 완성된 코드는 아래와 같다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main_12789 {
    static int n;
    static Queue<Integer> queue;
    static Stack<Integer> stack;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        queue = new LinkedList<>();
        stack = new Stack<>();

        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            queue.offer(Integer.parseInt(st.nextToken()));
        }

        int index = 1;

        while (!queue.isEmpty()) {
            if (queue.peek() == index) {
                queue.poll();
                index++;
            } else if (!stack.isEmpty() && stack.peek() == index) {
                stack.pop();
                index++;
            } else {
                stack.push(queue.poll());
            }
        }

        while (!stack.isEmpty()) {
            if (stack.peek() == index) {
                stack.pop();
                index++;
            } else {
                System.out.println("Sad");
                return;
            }
        }
        System.out.println("Nice");
    }
}