intro : ArrayDeque를 두개 사용하여 문제를 풀어가는게 포인트.

문제

인하대학교 학생회에서는 중간, 기말고사 때마다 시험 공부에 지친 학우들을 위해 간식을 나눠주는 간식 드리미 행사를 실시한다. 승환이는 시험 기간이 될 때마다 간식을 받을 생각에 두근두근 설레서 시험 공부에 집중을 못 한다. 이번 중간고사에서도 역시 승환이는 설레는 가슴을 안고 간식을 받기 위해 미리 공지된 장소에 시간 맞춰 도착했다. 그런데 이게 무슨 날벼락인가! 그 곳에는 이미 모든 학생들이 모여있었고, 승환이는 마지막 번호표를 받게 되었다. 설상가상으로 몇몇 양심에 털이 난 학생들이 새치기를 거듭한 끝에 대기열의 순서마저 엉망이 되고 말았다. 간식을 나눠주고 있던 인규는 학우들의 터져 나오는 불만에 번호표 순서로만 간식을 줄 수 있다고 말했다. 그제야 학생들이 순서대로 줄을 서려고 했지만 공간이 너무 협소해서 마음대로 이동할 수 없었다. 다행히도 대기열의 왼쪽에는 1열로 설 수 있는 공간이 존재하여 이 공간을 잘 이용하면 모두가 순서대로 간식을 받을 수 있을지도 모른다. 자칫 간식을 못 받게 될지도 모른다는 위기감을 느낀 승환이는 자신의 컴퓨터 알고리즘적 지식을 활용해 과연 모든 사람들이 순서대로 간식을 받을 수 있는지 확인하는 프로그램을 만들기로 했다. 만약 불가능 하다면 승환이는 이번 중간고사를 망치게 될 것 이고 가능하다면 힘을 얻어 중간고사를 잘 볼 수 있을지도 모른다. 사람들은 현재 1열로 줄을 서있고, 맨 앞의 사람만 이동이 가능하다. 인규는 번호표 순서대로만 통과할 수 있는 라인을 만들어 두었다. 이 라인과 대기열의 맨 앞 사람 사이에는 한 사람씩 1열이 들어갈 수 있는 공간이 있다. 현재 대기열의 사람들은 이 공간으로 올 수 있지만 반대는 불가능하다. 승환이를 도와 프로그램을 완성하라. 현재 간식 배부 공간을 그림으로 나타내면 다음과 같다.

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

입력

입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다. 다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,…,N) 순서가 앞에서부터 뒤 순서로 주어진다.

출력

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

문제 풀이 (틀린 방법)

위 코드에서 틀린 부분은 deque2에서 연속되어 stand와 일치하는값이 나올 수 있다는 경우의 수를 생각하지 못해서 틀린 로직을 구성하게 되었다. while문으로 stand값이 일치하는값이 존재한다면 remove를 해주어야 하는데 그부분을 놓쳤다.

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Deque<Integer> deque1 = new ArrayDeque<>();
        Deque<Integer> deque2 = new ArrayDeque<>();

        br.readLine();
        StringTokenizer st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) deque1.add(Integer.parseInt(st.nextToken()));


        int stand = 1;
        while (!deque1.isEmpty()) {
            Integer value = deque1.removeFirst();
            if (value == stand) stand++;
            else {
                if (!deque2.isEmpty()) {
                    if (deque2.peekFirst() == stand) {
                        deque2.removeFirst();
                        stand++;
                    } else deque2.addFirst(value);

                } else deque2.addFirst(value);

            }
        }

        for (Integer temp : deque2) {
            if (temp == stand) {
                deque2.removeFirst();
                stand++;
            } else break;
        }

        if (deque2.isEmpty()) bw.write("Nice");
        else bw.write("Sad");

        bw.flush();
        bw.close();
        br.close();
    }
}

문제 풀이 (112ms)

import java.io.*;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Deque<Integer> deque1 = new ArrayDeque<>();
        Deque<Integer> deque2 = new ArrayDeque<>();

        br.readLine();
        StringTokenizer st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) deque1.add(Integer.parseInt(st.nextToken()));

        int stand = 1;
        while (!deque1.isEmpty()) {
            Integer value = deque1.removeFirst();
            if (value == stand) {
                stand++;
                while (!deque2.isEmpty() && (deque2.peekFirst() == stand)) {
                    deque2.removeFirst();
                    stand++;
                }
            } else deque2.addFirst(value);
        }

        if (deque2.isEmpty()) bw.write("Nice");
        else bw.write("Sad");

        bw.flush();
        bw.close();
        br.close();
    }
}

문제 해석

위 문제는 큐 두개를 사용해서 풀이를 진행 할 수 있다. 주어진 예시를 잘 보면 1번 큐에서 2번 큐로의 값 이동은 가능하지만, 2번큐에서 1번 큐로의 이동은 불가하다. 그말은 1번큐에서의 값을 꺼내서 stand와 값이 일치하는지 확인하고, 일치한다면 remove 를 하고 혹시 2번 큐에서 다음 stand 값과 일치하는 값이 존재하는지 확인한다. 연속된 일치하는 값이 존재할 수 있으므로 while 문으로 반복하여 확인한다. 사실 이 문제에서 가장 중요한 부분은 언제 1번 큐에서 2번 큐로의 값을 이동시킬것인지와, 2번큐의 값을 언제 꺼내서 확인할 것인지 로직을 구성하는게 포인트가 되는 것 같다.

I am visible

contact

문제

입력

출력

문제 풀이 (틀린 방법)

문제 풀이 (112ms)

문제 해석