Passport Control

https://www.acmicpc.net/problem/16288

풀이

예전 icpc 서울 지역 예선에 나왔던 문제다.

처음 문제를 보고 큐에 진입하여 나오는 결과를 통해 답을 구하려 했다. 하지만 이렇게 할 경우 입력으로 들어온 결과와 비교하기 쉽지않고 경우의 수가 많아 어려움이 있었다.

결국 오랜 시간을 헤매다 약간의 힌트를 봤다.

핵심은 입력으로 들어온 값을 역으로 시행해서 큐에 넣는다고 생각하는 것이다. 큐의 반대기 때문에 스택을 이용한다고 볼 수 있다.

그렇게 입력 값들을 스택에 넣는데 만약 넣으려는 값이 스택의 값보다 작다면 불가능이라고 판단해 "NO"를 출력하고 그 외에는 "YES"를 출력한다.

또 설명을 스택으로 했는데 어짜피 참조해야할 값은 스택의 top이기때문에 스택의 탑만 기록할 사이즈가 k인 배열만 있으면 된다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
    static int n, m, k;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        k = Integer.parseInt(input[1]);

        int[] arr = new int[n];
        String[] line = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(line[i]);
        }

        int[] tops = new int[k];

        boolean available = true;
        loop:
        for (int i = 0; i < n; i++) {
            int num = arr[i];
            for (int j = 0; j < k; j++) {
                if (tops[j] == 0 || num > tops[j]) {
                    tops[j] = num;
                    continue loop;
                }
            }
            available = false;
            break;
        }

        if(available)
            bw.write("YES");
        else
            bw.write("NO");

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