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

문제

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

 

접근 방식

스택을 활용해서 풀 수 있는 문제다.

 

주어진 입력을 순회하면서 크게 두 가지 경우로 나누어 처리해 주면 되는데

바로 현재 입력값이 now와 같은지 다른지이다.

 

now는 1부터 시작하는 변수를 선언하여 해당 순서가

간식을 받을 때마다 1씩 증가시켜 주면서

다음 순서를 확인할 수 있게 해주는 변수다.

 

만약 현재 사람이 간식을 받을 순서가 맞다면 스택에 넣지 않고

그대로 now를 1 증가시켜 준 뒤에 남아있는 스택을 확인하면서

now와 일치하는 값이 있다면 뽑아주고 그렇지 않다면 넘어간다.

 

반대로 현재 사람이 받을 순서가 아니라면 스택에 넣어주기만 하면 된다.

 

예를 들어 3 2 1 순서로 줄을 서 있다면 3과 2는 스택에 들어가고

1이 간식을 받은 후에 2와 3의 순서대로 꺼내면 정렬된 순서를 만들 수 있다.

 

풀이

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[] arr = new int[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        Stack<Integer> s = new Stack<>();
        
        int now = 1;
        
        for (int i = 0; i < n; i++) {
            if (arr[i] == now) {
                now++;
                while (!s.isEmpty()) {
                    if (s.peek() == now) {
                        s.pop();
                        now++;
                    } else {
                        break;
                    }
                }
            } else {
                s.push(arr[i]);
            }
        }
        
        System.out.println(s.isEmpty() ? "Nice" : "Sad");
    }
}