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

 

 

 

문제

 

핵심만 설명하겠습니다.

 

승환이는 마지막 번호표를 받게 되었다.

설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다.

간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다.

 

 

그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다.

다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다.

자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 

 

 

사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다.

인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다.

이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다.

 

 

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

 

출처 : https://www.acmicpc.net/problem/12789

12789번: 도키도키 간식드리미

 

 

 

 

 

입, 출력

 

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

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

 

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

 

// 입력
5
5 4 1 3 2

// 출력
Nice

 

 

 

 

 

 

풀이

 

나는 문제를 봤을 때 현재 줄 순서대로 진행했다가 현재줄에 사람들이 다 빠지며 마지막에서야 대기줄 순서대로 나오게 하는 줄 알았다.

그래서 풀이를 진행하는 와중에 틀렸다고 나와서 어디가 틀렸는지 모르고 있었다.

 

문제의 핵심은 번호표에서 숫자가 높은 사람은 현재줄에서 대기줄(Stack)으로 이동해 대기 줄과 현재 줄의 번호표를 확인하여 순서대로 간식을 준다는 내용이였다. 

 

예를 들면, 번호표 순서가 3 2 1 5 4 라고 했을 때  번호표 1번 사람을 찾고 있는데 3, 2 가 앞에 있으므로 3, 2 순서대로 대기줄 (Stack)에 들어가고 현재줄에 서있는 사람과 대기줄에 있는 사람의 번호표를 계속 비교해 나간다는 소리이다. 

 

아래 그림을 보면 대기줄에 이동한 사람과 현재 줄에 있는 사람을 비교(녹색 동그라미) 해서 현재 번호표인 사람을 찾는 다는 소리이다.

 

 

 

 

코드로 보면, 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

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());

        // 현재 간식 줄라는 번호표
        int index = 1;
        String result = "Nice";		// 현재 줄이 제대로 서있을 수 있으므로 기본 값 Nice
        String[] sArr = br.readLine().split(" ");
        Stack<Integer> stack = new Stack<>();

        // 현재 줄 + 대기 줄 사람 처리
        for(int i = 0; i < N; i++){
            int currentNum = Integer.parseInt(sArr[i]);
            if(index != currentNum){
                if(!stack.isEmpty() && index == stack.peek()){
                    index++;
                    i--;
                    stack.pop();
                } else {
                    stack.push(currentNum);
                }
            } else {
                index++;
            }
        }

        // 대기줄에 있는 사람 처리
        while(!stack.isEmpty()){
            int pop = stack.pop();
            if(pop == index){
                index++;
            } else {
                result = "Sad";
                break;
            }
        }
        System.out.println(result);
    }
}

 

 

 

 

 

감사합니다.