[P&B] #107 BAEKJOON 12789

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

문제 설명

인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다.

그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다.

사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라.

현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.

위 예제는 다음 그림과 같이 움직였을 때 모두가 순서대로 간식을 받을 수 있다..

 

입력

입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.

다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.

 

출력

승환이가 무사히 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다.

 

나의 문제 풀이 코드

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

public class bj12789 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        Stack<Integer> studentStack = new Stack<>();
        String[] num = br.readLine().split("");
        int number = 1;

        for (int i = 0; i < N; i++) {
            int n = Integer.parseInt(num[i]);
            while (!studentStack.isEmpty() && studentStack.peek() == number) {
                studentStack.pop();
                number++;
            }

            if (n == number) {
                number++;
            } else {
                studentStack.push(n);
            }
        }

        while (!studentStack.isEmpty() && studentStack.peek() == number) {
            studentStack.pop();
            number++;
        }

        if (number == N + 1)
            System.out.println("Nice");
        else
            System.out.println("Sad");
    }
}

 

문제 풀이 코멘트

간식을 나눠주는 행사에서 학생들이 주어진 순서대로 간식을 받을 수 있는지 여부를 판단하는 프로그램을 작성하는 것을 요구합니다. 학생들은 대기열에 있으며, 맨 앞의 학생만 이동할 수 있고, 다른 학생들은 오른쪽으로만 이동할 수 있는 상황입니다.

• 우선 대기열의 순서를 확인하면서 현재 맨 앞에 있는 학생이 주어진 순서대로인지 확인합니다.
• 만약 현재 맨 앞에 있는 학생이 주어진 순서대로라면, 해당 학생을 대기열에서 제거합니다.
• 그렇지 않다면, 현재 맨 앞에 있는 학생을 대기열의 맨 뒤로 이동시킵니다.
• 이 과정을 반복하면서 모든 학생이 주어진 순서대로 나열되거나, 나열될 수 없는 경우를 판단합니다.

 코드를 보면 스택이 하나 선언되어 있습니다. 이 스택은 현재 줄 서 있는 곳이 아닌, 한 명씩만 설 수 있는 공간을 의미합니다.

 스택의 이론으로 모든 학생들이 받을 수 있는지만 확인하면 되기때문에 도착한 학생들의 번호를 입력받는 과정에서 number라는 변수를 1로 초기화 해둡니다. number 변수는 다음에 기대되는 학생의 번호를 나타내는 변수입니다. 처음에는 1번 학생을 기대하므로 1로 초기화해두는 것입니다.

  for문에서는 우선적으로 스택이 비어있지 않고, 스택의 맨 위에 있는 학생 번호가 number와 같다면, 스택에서 해당 학생을 제거하고 number를 증가시킵니다. 이것은 스택에 들어가있는 맨 위에 있는 순서대로 도착한 학생을 처리하는 부분입니다.

 스택을 검사하고 난 뒤에는 현재 도착한 학생의 번호 n과 기대되는 학생의 번호 number를 비교합니다. 만약 도착한 학생의 번호가 기대되는 학생의 번호와 같다면, 다음 학생을 기대하기 위해 number를 증가시킵니다. 그렇지 않으면 현재 학생을 스택에 추가합니다.

 for문을 다 돌고 나면 stack에는 간식받지 못한 학생들이 남아있을 것이고, number 역시 N+1 이 아닌 현재 간식을 받은 학생들 다음의 번호가 저장되어 있을 것입니다. 그래서 스택이 비거나 스택의 맨 위에 있는 원소가 number와 같지 않을 때까지 while 반복문을 사용하여 스택에 남아있는 순서대로 도착한 학생을 처리합니다.

 while문이 끝난 뒤에 모든 학생이 간식을 받았다면 number는 N + 1이어야합니다.  number는 초기에 1로 시작하고, 학생들이 주어진 순서대로 간식을 받을 때마다 1씩 증가합니다. 따라서 number가 N + 1이 되면 모든 학생들이 주어진 순서대로 간식을 받았다는 것을 의미합니다. 즉, 모든 학생들이 순서대로 나열되어 간식을 받았을 때, number가 N + 1이 되어 "Nice"를 출력합니다.