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

안녕하세요 :)

적어도 하루 1개 이상 알고리즘 문제를 해결하려 노력하고 있습니다.

혼자 해결 가능한 문제도 있고, 어려웠던 문제도 있던 차라 복습하고자  글을 써 내려갑니다.

 

---

 

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

오늘 문제는 학생들이 줄을 서 있는데 간식을 받을 수 있는 규칙은 단 하나,

1번부터 번호 순서대로 간식을 받아야 합니다.

하지만 학생들이 순서 없이 줄을 서 있어서 간식을 받지 못하는 학생은 한 명씩 대기 공간(스택)에 잠시 대기할 수 있습니다.

이 대기 공간은 마지막에 들어온 학생이 먼저 나오는 구조(스택)입니다.

스택과 큐에 대한 설명이 필요하신분들은 아래 링크에서 확인바랍니다.

[Algorithms] 자료구조 - 스택(Stack), 큐(Queue), 덱(Deque)

 

 

📘 문제

 

💡 해결 방법

현재 줄 서 있는 학생들은 Queue에 넣고, 임시로 대기하는 학생들은 Stack에 넣습니다.

order라는 변수를 통해 지금 간식을 받을 차례인 번호를 기억합니다.

 

✅ 풀이 및 설명 (설명은 더보기 클릭)

• 줄의 앞 번호가 간식 받을 순서라면 Queue에서 꺼냄
• 스택의 위 번호가 간식 받을 순서라면 Stack에서 꺼냄
• 순서가 아니라면 Queue에서 Stack으로 이동

import java.io.IOException;
import java.io.BufferedReader;
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());
        StringTokenizer st = new StringTokenizer(br.readLine());

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

        Stack<Integer> stack = new Stack<>();
        int order = 1;

        // 줄에도 사람 있거나, 대기 공간에도 사람이 있다면 계속 시도
        while (!queue.isEmpty() || !stack.isEmpty()) {
            if (!queue.isEmpty() && queue.peek() == order) {
                queue.poll();  // 줄에서 바로 간식 받기
                order++;
            } else if (!stack.isEmpty() && stack.peek() == order) {
                stack.pop();   // 대기 스택에서 간식 받기
                order++;
            } else if (!queue.isEmpty()) {
                stack.push(queue.poll());  // 대기 스택으로 이동
            } else {
                break;  // 어떤 행동도 못하면 종료
            }
        }

        System.out.print(stack.isEmpty() ? "Nice" : "Sad");
        br.close();
    }
}

 

이 문제는 단순히 큐나 스택 하나만 사용하는 것이 아니라

큐와 스택을 동시에 사용하여 상태를 시뮬레이션해야 하는 것이 포인트였습니다.

실제로 우리가 마주치는 문제 중에서도 한 곳에서 데이터를 처리하다가 임시 저장소에 옮기고,

다시 순서대로 꺼내야하는 상황이 종종 있으니 이 문제를 통해 그 감각을 익히기 좋습니다!

 

---

공부하면서 유용했던 부분 메모 겸 공유하고자 끄적입니다.

고쳐야 하는 부분 있다면 댓글 남겨주시면 수정하겠습니다.

행복한 하루 보내세요 (❁´◡`❁)