백준 10775 [공항] 파이썬

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

 

# 백준 10775 공항 문제
# bisect_left를 이용해 현재 비어 있는 게이트 중에서 조건에 맞는 게이트를 찾고,
# 해당 게이트를 배정한 후 리스트에서 제거하는 방식으로 구현.

import sys
from bisect import bisect_left

input = sys.stdin.readline

G = int(input())  # 게이트 수
P = int(input())  # 비행기 수

# 현재 비어있는 게이트 목록 (0 ~ G-1까지)
open_gates = [i for i in range(G)]
ans = 0  # 도킹 성공한 비행기 수

for _ in range(P):
    # 비행기가 도킹할 수 있는 최대 게이트 번호(입력은 1부터 시작하므로 -1 해줌)
    selectable_gate = int(input()) - 1

    if open_gates:  # 비어있는 게이트가 남아있는 경우
        # bisect_left: selectable_gate 이상인 게이트의 인덱스를 찾음
        idx = bisect_left(open_gates, selectable_gate)

        if idx == len(open_gates):
            # selectable_gate보다 큰 게이트만 있는 경우 → 제일 마지막 게이트 사용
            open_gates.pop()
        elif open_gates[idx] == selectable_gate:
            # 정확히 해당 게이트가 비어있는 경우 → 그 자리 사용
            open_gates.pop(idx)
        elif open_gates[idx] > selectable_gate:
            # selectable_gate보다 큰 게이트만 남은 경우 → 바로 앞 게이트 사용
            if idx - 1 < 0:  # 앞 게이트가 없으면 도킹 불가 → 종료
                break
            open_gates.pop(idx - 1)

        ans += 1  # 도킹 성공 시 카운트 증가
    else:
        # 비어있는 게이트가 없으면 종료
        break

print(ans)  # 최종적으로 도킹한 비행기 수 출력

 

생각보다 입력값의 범위가 크지 않아서 (1~10,000) 이분탐색으로 해결했다.

 

GPT는 UNION-FIND로 해결하였다. 확실히 시간이 5배정도  차이가 났다.(이분탐색: 0.5s, union-find: 0.1s)

 

# 백준 10775 공항 - Union-Find (Disjoint Set) 풀이
# 시간복잡도: O(P α(G)) - 사실상 O(P)와 동일하게 동작

import sys
input = sys.stdin.readline

# Find 함수: 경로 압축 적용
def find_parent(x):
    if parent[x] != x:
        parent[x] = find_parent(parent[x])
    return parent[x]

# Union 함수: 게이트 점유 후, 바로 왼쪽 게이트와 연결
def union(a, b):
    a = find_parent(a)
    b = find_parent(b)
    parent[a] = b  # b를 a의 부모로 설정 (왼쪽 게이트로 연결)

G = int(input())  # 게이트 수
P = int(input())  # 비행기 수

# 부모 배열 초기화 (자기 자신을 부모로 설정)
parent = [i for i in range(G+1)]

ans = 0
for _ in range(P):
    g = int(input())  # 비행기가 도킹할 수 있는 최대 게이트 번호

    # g 게이트의 루트(가장 가까운 비어있는 게이트) 찾기
    root_gate = find_parent(g)

    if root_gate == 0:
        # 0이면 더 이상 도킹할 수 있는 게이트가 없음
        break

    # 해당 게이트에 도킹 후, 왼쪽 게이트와 합치기
    union(root_gate, root_gate - 1)
    ans += 1

print(ans)

확실히 union-find가 직관적이어서 좋은거같다.