[BOJ/Java] 도키도키 간식드리미 (12789)

도키도키 간식드리미 (12789)

1. 문제 분석

문제 개요

• 학생들이 한 줄로 서서 간식을 받기 위해 대기하고 있다. 간식을 받는 순서는 1번부터 N번까지이며, 순서대로 간식을 받아야 한다.
• 그러나 학생들이 제멋대로 서 있기 때문에 순서대로 간식을 배분하기 어려울 수 있다. 간식을 주는 보조 스택을 사용해 순서를 맞출 수 있는지 확인하는 문제다.

입력 형식

• 첫 줄에 학생의 수 N이 주어진다.
• 두 번째 줄에 1부터 N까지의 학생 번호가 공백으로 구분되어 주어진다.

출력 형식

• 모든 학생이 순서대로 간식을 받을 수 있으면 "Nice", 그렇지 않으면 "Sad"를 출력한다.

2. 알고리즘 종류

이 문제는 스택을 이용한 시뮬레이션 문제로, 주어진 순서에서 스택을 사용해 학생들이 순서대로 간식을 받을 수 있는지 확인하는 방식으로 해결할 수 있다.

3. 주요 부분 및 코드 작성 방법

1. 스택 사용

• 현재 학생 번호가 순서에 맞지 않으면 스택에 넣고, 맞으면 간식을 배분한다.
• 간식을 배분한 후 스택에서 배분할 수 있는 간식이 있는지 확인한다.

2. 현재 순서와 스택의 최상단 비교

• 스택의 최상단이 현재 순서와 일치하면, 스택에서 제거하며 간식을 배분한다.

4. 코드 설명

메인 함수 (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());
    cnt = 1;

    for(int i = 0; i < N; i++) {
        int num = Integer.parseInt(st.nextToken());
        if(cnt != num) stack.push(num); // 현재 순서와 맞지 않으면 스택에 저장
        else {
            cnt++; // 현재 순서와 맞으면 간식 배분
            check(); // 스택에서 간식 배분 가능 여부 체크
        }
    }

    check(); // 남은 스택 처리
    if(stack.isEmpty()) System.out.println("Nice"); // 스택이 비어 있으면 모든 간식 배분 완료
    else System.out.println("Sad"); // 스택에 남은 간식이 있으면 순서대로 배분 불가능
}

• 입력을 받아 학생들의 순서를 확인하고, 현재 순서에 맞지 않는 학생은 스택에 넣는다.
• 순서에 맞는 학생이 간식을 받으면 check() 함수를 호출해 스택에서 배분 가능한 간식을 처리한다.
• 모든 처리가 끝난 후 스택이 비어 있으면 "Nice", 그렇지 않으면 "Sad"를 출력한다.

스택 체크 함수 (check)

public static void check() {
    while(!stack.isEmpty()) {
        if(cnt == stack.peek()) { // 스택의 최상단 간식이 현재 순서와 맞으면
            stack.pop(); // 간식 배분
            cnt++;
        }
        else break; // 순서와 맞지 않으면 중지
    }
}

• 스택의 최상단에 있는 학생이 현재 간식을 받을 순서와 맞으면 간식을 배분한다.
• 순서가 맞지 않으면 더 이상 간식을 배분할 수 없으므로 루프를 종료한다.

5. 전체 코드

package BOJ.BOJ12789_240824;

import java.util.*;
import java.io.*;

public class Main {
    static Stack<Integer> stack = new Stack<>();
    static int cnt;

    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());
        cnt = 1;

        for(int i = 0; i < N; i++) {
            int num = Integer.parseInt(st.nextToken());
            if(cnt != num) stack.push(num); // 현재 순서와 맞지 않으면 스택에 저장
            else {
                cnt++; // 현재 순서와 맞으면 간식 배분
                check(); // 스택에서 간식 배분 가능 여부 체크
            }
        }

        check(); // 남은 스택 처리
        if(stack.isEmpty()) System.out.println("Nice"); // 스택이 비어 있으면 모든 간식 배분 완료
        else System.out.println("Sad"); // 스택에 남은 간식이 있으면 순서대로 배분 불가능
    }

    public static void check() {
        while(!stack.isEmpty()) {
            if(cnt == stack.peek()) { // 스택의 최상단 간식이 현재 순서와 맞으면
                stack.pop(); // 간식 배분
                cnt++;
            }
            else break; // 순서와 맞지 않으면 중지
        }
    }
}