[BOJ/python]10775번 공항

백준 10775번 공항 파이썬

문제 링크

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)