[Python] 백준 10775 - 공항 문제 풀이

Overview

BOJ 10775번 공항 Python 문제 풀이
분류: Disjoint Set (분리집합), Union Find (유니언 파인드)

---

문제 페이지

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

---

풀이 코드 1 - 유니온 파인드

"""
해석하기 쉽게 고침
union, find 함수를 기본으로 사용
"""
from sys import stdin


parents = []


def find(x: int) -> int:
    if x == parents[x]:
        return x
    parents[x] = find(parents[x])
    return parents[x]


# 패러미터를 받을 때, x < y 이도록 받기
def union(x: int, y: int) -> None:
    x, y = find(x), find(y)
    parents[y] = x


def main():
    def input():
        return stdin.readline().rstrip()
    global parents

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

    parents = list(i for i in range(g + 1))
    cnt = 0
    for plane in planes:
        plane = find(plane)
        # 도킹 가능한 게이트가 없는 경우
        if plane == 0:
            break
        union(plane - 1, plane)
        cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()

비행기가 도킹할 때마다 find()로 도킹 가능한 게이트를 찾는다. 만약 find() 리턴값이 0이면 도킹 가능한 게이트가 없다는 뜻이다. 반대로 0보다 큰 값을 리턴하면 해당 값에 1을 뺀 값과 해당 값을 union한다.

---

풀이 코드 2 - 그리디 알고리즘(시간 초과)

from sys import stdin


def main():
   def input():
       return stdin.readline().rstrip()

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

   res = 0
   gates = [False] * (g + 1)
   for plane in planes:
       while plane > 0 and gates[plane]:
           plane -= 1

       if plane == 0:
           break
       gates[plane] = True
       res += 1

   print(res)


if __name__ == "__main__":
   main()

채점 결과 시간초과가 발생한 풀이이다.
비행기가 들어올 때마다 도킹 가능한 게이트 중에서 값이 가장 큰 게이트에 도킹하며 답을 구한다.