백준 10775 공항 문제풀이

문제 

https://www.acmicpc.net/workbook/view/2419

문제집: BOJ 길라잡이 베타 (2) (ryute)

 

 

 

문제 접근 방식

초기에 어떻게 풀지 감이 안와서 예제의 상황을 직접 풀어보았다. 게이트를 일차원 배열로 놓고 주어진 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 연관 자료구조 및 함수] 이런 흐름이었던 것 같다.