[백준 10775번] 파이썬 - 공항

백준 10775_공항

시간제한 1초(추가 시간 xx), 메모리 제한 256MB

조건

• 오늘은 신승원의 생일이다.
• 박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.
• 공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.
• 공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다.
  • 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.
• 신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력

• 첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.
• 두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.
• 이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력

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

접근 방법

시간초과 - 반복문

• 전체 게이트 수+1 크기의 리스트를 만들어준다.
• 비행기의 수만큼 반복문을 돌아준다.
  • 비행기가 도킹할 게이트 번호를 입력받고
  • 해당 게이트번호부터 0까지 -1 씩 범위를 잡고 순회한다.
  • 빈 게이트가 있는 경우 도킹, cnt += 1 break
• 반복문이 끝까지 순회하는 경우

    - break하고 종료

import sys

N = int(input())
M = int(input())

flight = [0] * (N+1)
cnt = 0
flag = False
for _ in range(M):
    val = int(input())
    for i in range(val, 0, -1):
        if flight[i] == 0:
            flight[i] = 1
            cnt += 1
            break
    else:
        flag = True
        break
    if flag:
        break
print(cnt)

분리집합 이용

• union - find를 사용하여 풀어준다.
• 딕셔너리로 0~전체 게이트 수만큼의 키 : 밸류를 만들어 준다.
  • {0:0, 1:1, 2:2, 3:3 ...}
  • 키의 경우 -> 현재 비행기가 들어올 수 있는 최대 게이트 번호
  • 밸류의 경우 -> 현재 게이트에 이미 비행기가 있어 주차할 수 있는 앞 게이트 번호
• find를 이용하여 주차할 게이트를 찾은 뒤, union을 이용해서 주차할 수 있는 게이트의 번호를 한 칸씩 앞으로 땡겨준다.
• find를 한 경우 0을 리턴한다면 현재 주차 불가능이므로 바로 break
• 즉, 예제 2번을 예 - 2 2 3 3 4 4 로 들어옴
  • 2번이 처음에 들어오면 find를 통해 2를 리턴하면서 자리가 있는 것을 확인한다.
    • 이후 union을 통해
    • {0:0, 1:1, 2:1, 3:3, 4:4}로 변경되며 2의 g를 가진 비행기가 들어오면 1번 게이트로 주차시키게 유도한다.
  • 2번이 또 들어온다면 2->1 번의 부모 비행기를 찾아가고 1을 리턴하므로 union 실행
    • union(1-1)을 실행하여 앞 번호의 게이트가 유도하는 주차 가능한 게이트 번호로 기록한다
    • {0:0, 1:0, 2:1, 3:3, 4:4} 가 된다.
  • 3번이 들어온다면 3을 리턴 후 union(2)를 실행
    • {0:0, 1:0, 2:0, 3:0, 4:4}
  • 3g를 가진 비행기가 들어왔지만 0번 게이트를 가르키므로 주차할 수 있는 게이트가 없다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
M = int(input())  

def find(x):  
    if parent[x] == x:  
        return x  
    P = find(parent[x])  
    parent[x] = P  
    return parent[x]  

def union(a):  
    b = find(a-1)  
    parent[a] = b  


parent = {i: i for i in range(N+1)}  
count = 0  
plane = [int(input()) for _ in range(M)]  

for i in plane:  
    val = find(i)  

    if val == 0:  
        break  
    union(val)  
    count += 1  

print(count)