공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다. P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기를 최대 몇 대 도킹시킬 수 있는가?
# 틀린 코드
순서대로 오는 비행기를 게이트에 도킹시킨다. 최대한 번호가 높은 게이트에 도킹시키고 도킹시키지 못한 경우 반복문을 탈출한다.
논리상 정답이지만 시간초과다. 숫자의 범위가 10^5 이기 때문에 시간초과가 나는건 당연하긴 하다.
그럼 반복문 한번만 돌라는 얘긴데 주어진 입력 이하의 게이트로 넣으라면서 반복을 안하고 게이트가 비어있는지 안비어있는지 어떻게 체크하라는거여?!??
import sys
input = sys.stdin.readline
G = int(input())
P = int(input())
planes = []
gates = [0] * G
for _ in range(P):
planes.append(int(input()))
for i in range(P):
flag = 0
for j in range(planes[i]-1, -1, -1):
if gates[j] == 0:
gates[j] = 1
flag = 1
break
if flag == 0:
break
print(sum(gates))# 참고 코드
인터넷을 참고하니 union-find 개념을 사용해야 한다고 한다. 처음듣는데???
먼저 코드설명은 다음과 같다.
parent 리스트를 만들어 index 값과 parent[index]값이 같으면 게이트가 빈 상태고, 다르면 도킹된 상태다.
빈 게이트에 주차하는 경우 parent[index]값을 1 감소시킨다.
게이트에 주차되어 있는 경우 find(x)가 아닌 find(parent[x])를 하여 숫자가 낮은 게이트를 찾는다.
코드는 이해가 되는데 개념이 생소해서 그런지 왜 이게 더 빠른지 이해가 잘 되지 않았다. 이중 for문 돌지 않는 대신 for문안에 재귀함수를 넣었다. 느리면 느렸지 재귀가 반복문보다 빠른 건 듣도보도 못했다. union-find 개념에 대해 자세히 알아보자.
import sys
input = sys.stdin.readline
answer = 0
G = int(input())
P = int(input())
parent = [i for i in range(G + 1)]
planes = []
for _ in range(P):
planes.append(int(input()))
def find(x):
if parent[x] == x:
return x
parent[x] = find(parent[x])
return parent[x]
for plane in planes:
docking = find(plane)
if docking == 0:
break
parent[docking] = parent[docking - 1]
answer += 1
print(answer)# Union-find
- 대표적 그래프 알고리즘으로 '합집합 찾기'라는 의미 존재.
- 상호 배타적 집합(Disjoint-set)
- 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘
find : x가 어떤 집합에 포함되어 있는지 찾는 연산
union : x와 y가 포함되어 있는 집합을 합치는 연산
모두 연결되지 않고 각자 자기 자신만을 집합의 원소로 가지고 있을 때, 모든 값이 자기 자신을 가리키도록 만든다.
즉, parent[i] = i
union : 부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합쳐짐.
1,2,3이 연결된 경우 '1과 3이 연결되었는지' 파악하기 위해 재귀함수가 사용된다.
