08_09 [기출문제] 탑승구

01 당장 좋은 것만 선택하는 그리디

02 아이디어를 코드로 바꾸는 구현

03 꼭 필요한 자료구조 탐색 알고리즘 DFS/BFS

04 기준에 따라 데이터를 정렬

05 범위를 반씩 좁혀가는 탐색

06 다이나믹 프로그래밍

07 가장 빠른 길 찾기

08 다양한 그래프 알고리즘

[문제]

공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다.

공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 gi번째 (1 <= gi <= G) 탑승구 중 하나에 영구적으로 도킹해야 합니다. 이때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있습니다.

또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중지합니다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 합니다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력하는 프로그램을 작성하세요.

[입력조건]

• 첫째 줄에는 탑승구의 수 G (1 <= G <= 100,000)가 주어집니다.
• 둘째 줄에는 비행기의 수 P (1 <= P <= 100,000)가 주어집니다.
• 다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 gi (1 <= gi <= G)가 주어집니다. 이는 i번째 비행기가 1번부터 gi번째 (1 <= gi <= G) 탑승구 중 하나에 도킹할 수 있다는 의미입니다.

[출력조건]

• 첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력합니다.

입력예시1

4
3
4
1
1

출력예시1

2

입력예시2

4
6
2
2
3
3
4
4

출력예시2

3