Q42. 탑승구

문제 참고

[이코테] 그래프 알고리즘 - 탑승구 (tistory.com)

[이코테] 그래프 알고리즘 - 탑승구

 

오.. 좀 어려운데?

 

일단 내생각은 이렇다.

비행기 도킹 정보를 받았을 때 해당 탑승구가 비어있으면 거기에 도킹하면 된다.

근데 안비어있으면 그보다 작은 넘버의 탑승구 중에서 비어있는걸 찾아 도킹시키면 된다.

만약 작은 넘버를 계속 찾아 내려갔는데 1번 탑승구마저 도킹이 되어있으면 그대 공항 운행을 중지한다.

이걸 naive하게 풀면 도킹할 수 있는 탑승구를 찾을 때마다 O(N)의 시간이 걸릴 것이다. (O(G))

비행기의 수가 P니까 이를 다 검사하려면 최대 O(G*P)의 시간이 걸릴 수 있는데

내생각에 탑승구 찾는 과정을 union-find로 해결하면 O(P * log G)로 줄일 수 있지 않을까 싶다.

 

비행기가 도킹할 수 있는 탑승구 정보 g_i가 주어질 때마다 다음과 같은 행동을 하면 문제를 풀 수 있지 않을까

1. g_i의 루트노드를 찾는다. root(i)라고 치자.

2. root(i)-1의 루트노드를 찾는다. 이 루트노드가 0이면 이미 탑승구가 다 찬것이므로 공항 운행을 중지한다.

만약 0이 아니라면 root(i)와 root(i)-1을 union한다.

 

이때 원소 i의 루트노드는 탑승구i에 가장 가까운 빈 탑승구를 의미한다. 그니까 root(i)가 0이 되면 1번부터 i까지 다 찬 상태를 의미한다. (좀 어렵나..)

 

정답지를 확인해보니까 내 설명과 정확히 일치한다!!!!

구현하기가 너무 귀찮다. 이것까지 구현하면 이틀동안 union find만 한 4번은 구현하는거같은데..

구현 난이도 쉽고 문제 아이디어도 알았으니까 이번문제는 슬쩍 넘어가보자..