😘 문제 요약
i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하고 이를 통해 도킹시킬 수 있는 최대의 비행기 수를 출력하여라
👏 key point
gi 가 주어진다면 되도록 gi 에 도킹하고 그럴 수 없다면 gi -1에 도킹하는 식으로 하려고 한다. 그렇게 해서 만약 gi -1이 0이 된다면 더 이상 도킹할 수 없는 방식으로 문제를 풀려고 시도 하였다.
😜 잘못된 나의 풀이
g = int(input())
p = int(input())
lst = []
for _ in range(p):
lst.append(int(input()))
visited = [False] * (g+1)
count = [0]
result = [0]
def check(k):
while k != 0:
if visited[k] == False:
visited[k] = True
count[0] += 1
break
else:
k -= 1
if k == 0:
result[0] = 1
for i in lst:
check(i)
if result[0] == 1:
break
print(count[0])
방문을 했다는 표시를 하기 위한 visited 그리고 만약 해당 게이트에 비행기가 있다면(visited[i] == True) -1번째 비행기를 조사한다. 이렇게 하여서 0번째 비행기를 조사하게 된다면 더 이상 도킹할 수 없다고 판단한다. 하지만 이러한 코드는 시간 초과의 오류가 계속 나타났다.
그렇다면 어떠한 알고리즘을 쓰는 것이 좋을까?
바로 union - find 알고리즘이다.
그렇다면 union-find 알고리즘은 무엇일까?disjoint set 자료구조로도 불리며 이는 공통원소가 없는 즉 상호베타적인 부분집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다.
쉽게 말해서 비슷한 특징들을 지닌다고 생각하는 목록들을 분류해놓고 이들간의 연관성은 없다라고 하는 것이다. 약간 흑백논리 같은 느낌이라고 생각하면 될 거 같다.(필자 생각)
그렇다면 union -find 는 무엇인가?
말 그대로 보자면 union -find는 찾고 합치는 과정입니다. find와 같은 경우 해당 집합을 대표하는 값을 찾는 것입니다. (이때 트리의 root를 생각하면 편한다.) union의 경우 해당 노드들 간의 관계를 정의 지어 주는 단계입니다. (트리에서 부모 자식 관계 정의를 생각하면 편하다.)
간단한 union-find 과정
다음 과 같은 방식을 구현하면 이전의 구현하던 코드보다 시간 복잡도를 훨씬 많이 줄일 수 있다. (앞선 코드의 경우 해당 노드가 어디에 방문할 것인지 하나하나씩 다 탐방했기 때문 - 이중 포문으로 -)
🤞 정답 코드
g = int(input())
p = int(input())
ap = []
for _ in range(p):
ap.append(int(input()))
def find(x):
if x == parent[x]: #부모 노드가 자기자신(아직 한번도 방문하지 않았다.)
return x
p = find(parent[x]) #각 노드의 부모 노드를 찾아 올라간다.
parent[x] = p
return parent[x]
def union(x,y):
x = find(x)
y = find(y)
parent[x] = y
parent = {i:i for i in range(g+1)}
cnt = 0
for i in ap:
x = find(i)
if x == 0: # 해당 노드(x)의 부모가 0이 되면 더 이상 도킹 x
break
union(x,x-1) # 해당 노드(x)의 부모를 (x - 1)의 부모로 설정
cnt += 1
print(cnt) 