파이썬 그리디 알고리즘 백준 10775 공항

문제

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

풀이

도킹은 1<= g <=비행기번호로 수행하기 때문에 가장 많이 도킹을 하기 위해서는

도킹 가능한 게이트 끝에서부터 채워 넣으면 된다.

하지만 이중반복문으로는  시간 초과가 나기 때문에 union-find를 이용해야 한다.

union-find는 부모를 연결하여 하나의 그래프를 만드는 것인데

우선 0부터 게이트수까지 딕셔너리를 생성한다.

두번째 예제로 살펴보면 0:0, 1:1, 2:2, 3:3, 4:4 이렇게 생성된다.

그리고 비행기번호로 반복문을 순회하여 2 2 3 3 4 4 비행기 정보를 사용한다.

비행기번호와 그 부모가 같은 경우 그대로 return하고 해당 비행기와 게이트는 도킹했다는 것을 나타내기 위해

unionParent함수를 통해 해당 비행기의 부모를 -1하여 앞 부분과 연결한다.

이 작업을 통해 딕셔너리는 0:0, 1:1, 2:1, 3:3, 4:4 로 변하게 되며

비행기 정보 중 2번째 2를 사용할 때 2의 부모를 찾아 1에 대해 unionParent를 수행해

0:0, 1:0, 2:1, 3:3, 4:4 로 바뀐다. 이렇게 되면 1번과 2번의 게이트를 사용한 것이며 만약 3번째 2가 있다면

2의 부모를 1로 찾고 또 1의 부모를 찾았을 때 0이 나온다. 이후 조건에 의해 반복문이 종료된다.

 

import sys
g = int(sys.stdin.readline().rstrip("\n"))
p = int(sys.stdin.readline().rstrip("\n"))
pLists = [int(sys.stdin.readline().rstrip("\n")) for _ in range(0,p)]

def findParent(x):
   if parent[x] == x:
       return x
   p = findParent(parent[x])
   parent[x]=p
   return parent[x]

def unionParent(x,y):
    x = findParent(x)
    y = findParent(y)
    if x<y:
        parent[y] = x
    else:
        parent[x] = y
# 이중 반복문으로는 시간 초과 => union-find이용
parent = {i:i for i in range(0,g+1)} #{0:0, 1:1, 2:2, 3:3, 4:4}
count=0
for pList in pLists:
    x = findParent(pList)
    if x==0:
        break
    unionParent(x,x-1)
    count+=1
print(count)