[코테] 백준 그리디 10775번 문제

10775번 : 공항

문제 링크

https://www.acmicpc.net/problem/10775

문제 설명

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

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

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

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

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

입력

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

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

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

출력

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

문제 풀이

이번에도 시간 초과의 벽에 부딫혔다.

첫 번째는 이중 반복문을 통해서 시도했을 때는 당연하게 시간 초과

두 번째는 index 메소드를 이용해 try, except를 사용하였느나 시간 초과

마지막으로는 인터넷 검색의 힘을 빌려서 검색한 결과 Union-Find 알고리즘을 사용해야 한다는 것을 알게 되었다. Union-Find는 Disjoint Set(중복되지 않는 부분 집합들)을 표현할 때 사용하는 알고리즘으로 트리 구조를 이용하여 구현한다.

참고 사이트 https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html https://2hs-rti.tistory.com/entry/%EB%B0%B1%EC%A4%80-10775%EB%B2%88-%EA%B3%B5%ED%95%AD-%ED%8C%8C%EC%9D%B4%EC%8D%AC

# 이중 반복문 사용 : 시간 초과
import sys

input = sys.stdin.readline

G = int(input())
P = int(input())
arr = [0] * G
airplane = []

for i in range(P) :
    airplane.append(int(input()))
    
for i in airplane :    
    before_state = sum(arr)
    print(arr)
    for j in range(i-1, -1, -1):
        if arr[j] == 0 :
            arr[j] = 1
            break
    if sum(arr) == before_state : break

print(sum(arr))

# try, except로 index 메소드 사용 : 시간 초과

import sys

input = sys.stdin.readline

G = int(input())
P = int(input())
arr = [0] * G
airplanes = []

for i in range(P) :
    airplanes.append(int(input()))
    
for airplane in airplanes : 
    try :
        arr[airplane - arr[airplane-1::-1].index(0) -1] = 1
    except : 
        break

print(sum(arr))

# union-find 알고리즘 사용 : 통과
def find_parent(x):
    if x != parent[x]:
        parent[x] = find_parent(parent[x])
    return parent[x]

def union_parent(x, y):
    x = find_parent(x)
    y = find_parent(y)
    if x < y:
        parent[y] = x
    else:
        parent[x] = y

G = int(input())
P = int(input())

parent = [i for i in range(G+1)]
plane = []
for _ in range(P):
    plane.append(int(input()))
    
count = 0
for p in plane:
    x = find_parent(p)
    if x == 0:
        break
    union_parent(x, x-1)
    count += 1

print(count)