백준 - Passport Control 16288

---

문제 분석

게이트 크기의 배열을 선언하고 배열에 현재수보다 큰수만 담아준다 

2번 케이스를 예로 들어보자

4 1 3 2 5 6 8 9 7 10

-----------------

배열[0] - 4

배열[1]

배열[2]

-----------------

배열[0] - 4

배열[1] - 1

배열[2]

-----------------

배열[0] - 4

배열[1] - 1 3

배열[2]

-----------------

배열[0] - 4

배열[1] - 1 3

배열[2] - 2

-----------------

배열[0] - 4 5

배열[1] - 1 3

배열[2] - 2

-----------------

배열[0] - 4 5 6

배열[1] - 1 3

배열[2] - 2

-----------------

배열[0] - 4 5 6 8

배열[1] - 1 3

배열[2] - 2

-----------------

배열[0] - 4 5 6 8 9

배열[1] - 1 3

배열[2] - 2

-----------------

배열[0] - 4 5 6 8 9

배열[1] - 1 3 7

배열[2] - 2

-----------------

배열[0] - 4 5 6 8 9 10

배열[1] - 1 3 7

배열[2] - 2

-----------------

 

배열에 넣을 곳이 없다면 NO 를 출력하고 끝낸다.

 

전체 소스

package test;

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

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int repeat = Integer.parseInt(st.nextToken());
		int gate = Integer.parseInt(st.nextToken());
		int[] array = new int[gate];

		st = new StringTokenizer(br.readLine(), " ");

		boolean check=false;
		for (int i = 0; i < repeat; i++) {
			int input = Integer.parseInt(st.nextToken());
			check = false;

			for (int j = 0; j < gate; j++) {
				if (array[j] < input) {
					array[j] = input;
					check = true;
					break;
				}
			}

			if (!check) {
				System.out.println("NO");
				break;
			}

		}
		if (check) {
			System.out.println("YES");
		}
	}

}

 

 

 

 

틀린 사례

처음 접근은 큐에 담은 후 현재수와 비교하는 방식으로 했다.

활용할 수 있는 게이트수를 계속 변경했다.

1. 현재와 비교해서 같으면 (꺼낼게 없으면) 넘겼다.

2. 현재와 다르다면 큐의 가장 앞에있는 수를 꺼내서 비교했다.

 

이런식으로 하니 조건이 너무 많이 붙었다.

package test;

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

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int repeat = Integer.parseInt(st.nextToken());
		int gate = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine(), " ");

		PriorityQueue<Integer> q = new PriorityQueue<>();
		int now = 1;
		int max = 0;
		for (int i = 1; i <= repeat; i++) {
			int input = Integer.parseInt(st.nextToken());
			if (now == input) {
				now++;
				while (!q.isEmpty()) {
					int compare = q.poll();
					if (now == compare) {
						now++;
						gate++;
					} else {
						q.offer(compare);
						break;
					}
				}
			} else if (now != input) {
				if (!q.isEmpty()) {
					int compare = q.poll();
					if (now == compare) {
						gate++;
						now++;
					} else {
						q.offer(compare);
						if (max < input) {
							max = input;
							q.offer(input);
						} else {
							q.offer(input);
							gate--;
						}
					}
				} else {
					max = input;
					q.offer(input);
					gate--;
				}

			}
			System.out.println(gate);
			if (gate == 0) {
				System.out.print("NO");
				return;
			}

		}

		System.out.println("YES");
	}

}

 

 

 

---

문제

그림 G.1: N명의 입국 승객은 k개의 여권 심사 창구 {Qk} 중 하나를 반드시 거쳐야 한다.

N명의 입국 승객이 여권 심사를 위하여 그림 G.1 과 같이 입국 대기 줄에서 [1, 2, … , N − 1, N] 순서로 기다리고 있다. 입국 승객은 준비된 k개의 여권 심사 창구 중 하나를 통과한 뒤 공항을 빠져나갈 수 있다. 입국할 때의 줄 선 승객의 순서를 [1, 2, … , N − 1, N]이라고 할 때 k개의 여권 심사 창구를 통과하여 입국장을 빠져나가는 순서 [π1, π2, … πN−1, πN]는 처음과 달라질 수 있다. k개 여권 심사 창구가 준비되어 있을 때, 이 입국장을 빠져나가는 순서가 가능한 순서인가를 계산해야 한다.

예를 들어 설명해보자. 만일 N = 3, k = 2라고 할 때 입국장을 빠져나가는 순서 중 [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]는 가능하지만 [3, 2, 1]은 불가능하다. 여러분은 입국장을 빠져나가는 순서 [π1, … , πN]가 입력으로 주어질 때, 이 순서가 가능하면 YES 를, 불가능하면 NO 를 출력해야 한다. 단, 특정 큐에 줄을 선 상황에서는 승객들의 순서를 임의로 바꿀 수는 없다. 그리고 각 여권 심사 창구에 준비된 큐는 N명 승객이 모두 들어올 정도로 충분히 크다고 가정한다.

입력

입력은 표준입력을 사용한다. 첫 번째 줄에는 두 개의 정수 N 과 k 가 주어진다. N은 입국 승객의 수이며 k는 여권 심사 창구의 수이다. 단, 2 ≤ k ≤ N ≤ 100 이다. 그리고 두 번째 줄에는 승객이 입국장을 빠져 나가는 순서 [π1, … , πN]가 주어진다.

출력

출력은 표준출력을 사용한다. 입력으로 주어진 순서 [π1, … , πN]대로 입국장을 빠져나가는 것이 가능하면 YES 를 출력하고, 아니면 NO 를 출력해야 한다.

예제 입력 1 복사

3 2
3 2 1

예제 출력 1 복사

NO

예제 입력 2 복사

10 3
4 1 3 2 5 6 8 9 7 10

예제 출력 2 복사

YES

출처