문제
https://www.acmicpc.net/workbook/view/2419
문제집: BOJ 길라잡이 베타 (2) (ryute)
www.acmicpc.net
문제 접근 방식
초기에 어떻게 풀지 감이 안와서 예제의 상황을 직접 풀어보았다. 게이트를 일차원 배열로 놓고 주어진 k 게이트를 입력받아 도킹을 시켜본다. 예제를 따라해보니 비행기를 최대로 넣기 위해서는 k 번째 이하의 '비어있는 게이트' 중 k 와 가장 가까운 게이트를 선택해야 비행기를 최대로 도킹할 수 있다는 결론을 얻게 되었다.
비행기 도킹 최대 >> k 번째 게이트와 가장 가까운 빈 게이트에 도킹을 시킨다.
p 개의 게이트가 주어졌을 때, 가장 가까이 있는 빈 게이트를 찾아서 넣어주면 된다. 이를 위해서 free_gate_list 라는 일차원 배열에 각 게이트 별 가장 가까운 빈 게이트를 저장해놓음으로써 free_gate_list[gate] 에 접근하면 도킹 가능한 게이트를 찾을 수 있도록 하였다.
또한, k 번째에 도킹을 했다면 k-1 번째의 도킹 가능한 위치(free_gate_list[gate])로 k번째의 도킹 가능 위치를 갱신해주도록 구현을 했다. 이렇게 함으로써 k 게이트가 주어졌을 때, 도킹 가능한 게이트를 찾고(find), 도킹을 시킨 후 도킹 가능한 게이트를 갱신(union) 하여 비행기가 최대로 들어갈 수 있도록 구현을 했다.
시간 복잡도
각 게이트에서 비행기의 빈 공간을 찾고, 도킹을 하는 과정의 시간복잡도는 O(1) 이며, P개의 비행기가 주어지므로 O(P) 의 시간이 걸린다. P의 최댓값이 1e5 이므로 제한 시간 내에 동작한다.
코드
import sys
# 현재 입력 받은 gate와 가장 가까운 위치의 빈 게이트(도킹 가능한 게이트)를 찾는다.
# free_list[gate] = gate 인 곳이 빈 게이트이다.
def find_free_gate(free_list,gate):
if free_list[gate]==gate:
return gate
free_list[gate]=find_free_gate(free_list,free_list[gate])
return free_list[gate]
if __name__=='__main__':
li=list(map(int,sys.stdin.read().splitlines()))
g=li.pop(0)
p=li.pop(0)
# free_list[k] = k 게이트를 기준으로 빈 게이트(도킹 가능한 게이트)를 가르킨다.
free_list=[i for i in range(g+1)]
answer=0
for gate in li:
# gate 를 기준으로 빈 공간을 찾는다
free = find_free_gate(free_list,gate)
# 빈 게이트가 없다면 중단한다(공항 폐쇄).
if free==0:
break
# 빈공간에 도킹한다
# 도킹 후, (빈공간-1)이 가르키는 빈 공간으로 덮어쓴다(빈공간 위치 갱신)
free_list[free] = find_free_gate(free_list,free - 1)
answer+=1
print(answer)
회고
문제를 보고 풀 때는 Union Find 문제라는 느낌은 없었다. 그래프 또는 트리 형태의 자료구조가 나오는 것도 아니었고, 집합 관련 문제도 아니었기 때문이다. 하지만 풀이과정에서 일차원 배열을 통해 특정 지점을 가르키고 있는 자료구조( Union Find 의 parents) 가 필요했고, 해당 자료구조를 통해 비어있는 게이트를 찾는 로직(Union Find의 find_parent 함수), 그리고 비어있는 게이트를 갱신하는 로직(Union Find의 union 함수) 이 필요했다. Union Find의 자료구조 및 함수들이 모두 사용되었다. 사고를 하는 과정이 [문제 = Union Find 문제] 라기 보다는 [ 문제 > 풀어보니 모두 Union Find 연관 자료구조 및 함수] 이런 흐름이었던 것 같다.
'문제풀이 > 백준' 카테고리의 다른 글
백준 1976 여행가자 문제풀이 (0) | 2024.01.22 |
---|---|
백준 4195 친구 네트워크 문제풀이 (1) | 2024.01.22 |
백준 1717 집합의 표현 문제풀이 (0) | 2024.01.20 |
백준 1916 최소비용 구하기 문제풀이 (0) | 2024.01.19 |
백준 1865_웜홀 문제풀이 (0) | 2024.01.17 |