-
[BOJ/python]10775번 공항알고리즘/BOJ 2022. 7. 4. 22:26
백준 10775번 공항 파이썬
문제 링크
한 번에 푼 문제는 아니지만 단계적으로 잘 풀어서 기분이 좋았다. 유니온 파인드를 이용해서 풀어야 하는 문제다.
처음에는 그리디하게 가능한 가장 번호가 큰 공항에 비행기를 배치했다. 새로운 비행기에 할당된 공항이 중복되면 기존에 있던 비행기는 왼쪽으로 한 칸씩 밀어서 배치가 가능하다. 이를 이중 반복문을 통해 구현했다.
1. 코드 (greedy, 시간 초과)
# 공항 G, P = int(input()) , int(input()) airport = [-1 for _ in range(G+1)] ans=0 for i in range(P): g= int(input()) if airport[g] == -1: airport[g]=1 ans+=1 else: check = ans for j in range(g,0,-1): if airport[j] == -1: airport[j]=1 ans+=1 break if ans==check: print(ans) break
당연히 시간초과가 발생했다.
2-1. union - find풀이
빈 공항 중 가장 오른쪽에 있는 칸을 찾는 방법은 유지한채 시간을 줄일 수 있는 방법을 생각했다. 반복문을 사용하지 않고 union-find를 통해 중복된 공항을 선택하면 O(1)시간으로 비어있는 공항을 알려주는 알고리즘을 떠올렸다.
현재 공항보다 작은 숫자의 공항 중에서 가장 오른쪽에 비어있는 칸을 루트로 union한다. 이렇게 되면 여전히 greedy하게 공항을 배치할 수 있으며 중복된 공항을 선택하면 가능한 공항 중 가장 큰 번호를 find를 통해 알려준다.
ex)1번에서 7번까지 공항이 있고, 3번 6번 7번에 이미 greedy하게 배치된 경우를 가정하자.
2(root)-3 / 5(root)-6-7 과 같이 트리가 만들어진다.(find를 통해 7번의 부모 노드는 5번이 된다.)
이 때 다음 비행기가 7번 게이트를 가려고 하면 5번 게이트를 O(1)에 찾을 수 있게 된다.
어떠한 공항에도 도킹할 수 없는 경우는 find를 했지만 0번 노드를 반환한 경우이다.
2-2. 코드 (union-find + greedy)
# 공항 def find(u): if p[u]<0: return u p[u]=find(p[u]) return p[u] def union(u,v): # u가 루트 u,v = find(u),find(v) if u==v : return p[v]=u G, P = int(input()) , int(input()) p=[-1 for i in range(G+1)] ans=0 for i in range(P): g= int(input()) target = find(g) if target==0: break union(target-1, target) ans+=1 print(ans)
'알고리즘 > BOJ' 카테고리의 다른 글
[BOJ/python]3020번 개똥벌레 (0) 2022.07.04 [BOJ/python]1092번 배 (0) 2022.07.04 [BOJ/python]1765번 닭싸움 팀 정하기 (0) 2022.07.03 [BOJ/python] 6987번 월드컵 (0) 2022.07.01 [BOJ/python] 2412번 암벽 등반 (0) 2022.07.01