공항 ( 10775 번 )

10775번: 공항

 

---

🧠 알고리즘

• 유니온 파인드 기반의 그리디 시뮬레이션

 

✔️ 동작 방식

• 각 게이트를 자기 자신으로 초기화한 배열 check를 사용하여 도킹 가능한 게이트를 관리
• 비행기가 i번째에 도착하면, 해당 비행기가 도킹 가능한 가장 큰 번호의 게이트(1 ~ gi 중 최대)를 _find_root()로 찾음
• 해당 게이트가 도킹 가능하면 _union(root, root - 1)을 수행하여, 현재 게이트는 사용 처리하고 다음 가능한 게이트를 연결
• 도킹할 게이트가 없으면 (find_root == 0), 공항 폐쇄 → 현재까지 도킹한 비행기 수 return
• 모든 비행기가 도킹되면 p 리턴

---

 

🧾 코드

import sys

def _find_root(num):
    global check
    if num != check[num]:
        check[num] = _find_root(check[num])
    return check[num]

def _union(x, y):
    global check
    x_root, y_root = _find_root(x), _find_root(y)
    check[x_root] = y_root

def _main(gate, p):
    global check
    check = [i for i in range(gate + 1)]

    for count in range(1, p + 1):
        g = int(sys.stdin.readline().rstrip())
        find_root = _find_root(g)

        if find_root == 0:
            return count - 1
        
        _union(find_root, find_root - 1)

    return p


gate = int(sys.stdin.readline().rstrip())
p = int(sys.stdin.readline().rstrip())

print(_main(gate, p))

---

 

⏱️ 시간 복잡도

for count in range(1, p + 1) : 들어오는 비행기 만큼 순회 ( 선형 시간 )
	# find 및 union은 경로 압축 기반 >> 거의 상수
	_find_root
    _union
    
해당 알고리즘 시간 복잡도 : 선형 시간 복잡도 ( O(n) )