백준 10775 공항

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

순차 탐색을 그리디(?)하게 탐색하는 방식을 사용해서 풀었다. (???)

게이트에 도킹하는 규칙은 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트 중 하나에 도킹하는 것이므로, gi부터 1번 순으로 도킹하는 게 가장 효율적이다.
1번부터 채울 시, n번 비행기가 m번째 게이트에 도킹할 경우, 그 다음 비행기들은 최소 m+1번 이상이어야 끝나지 않고 계속 도킹할 수 있다.

순차탐색을 더 빠르게 사용하기 위해 union-find에서 find를 활용했다.
10^5의 범위를 가지기 때문에 두개의 리스트를 이용해 탐색하는 방법이 가능했다.
하나는 빠르게 탐색하기 위해 비어있는 인덱스로 이동시키는 리스트, 다른 하나는 내용물이 차있는지 확인하는 리스트이다.

def find(n):
    if dock[n] == n:
        return n
    dock[n] = find(dock[n])
    return dock[n]

재귀적으로 탐색 후 값을 갱신시켜 준다.

p의 범위가 g보다 클 수 있으므로, 각 비행기가 들어갈 수 있는 게이트의 번호는 min(p, gi) (gi는 비행기번호)가 된다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

def find(n):
    if dock[n] == n:
        return n
    dock[n] = find(dock[n])
    return dock[n]

g = int(input())
p = int(input())
plane = [int(input()) for _ in range(p)]

dock = list(range(g+1))
gate = [0] * (g+1)

cnt = 0
for i in range(p):
    tmp = find(min(plane[i], g))
    if tmp != 0 and gate[tmp] == 0:
        gate[tmp] = 1
        dock[tmp] -= 1
        cnt += 1
    else: break

print(cnt)

만약 도킹 실패시 즉시 종료한다는 조건을 무시해서 한 번 틀렸다...