Search

탑승구

문제 : 탑승구

풀이

해결에 필요한 핵심 아이디어: 그리디, 서로소 집합 알고리즘

그리디 알고리즘
도킹 비행기 수를 최대로 하기 위해선 비행기가 도착했을 때 해당 번호(도킹 가능한 가장 큰 번호)의 게이트에 도킹하는 것이 유리
3 - 2 - 1 순으로 비행기가 도착한다고 가정했을 때, 3번 비행기가 3번 게이트를 놔두고 굳이 2번이나 1번으로 도킹할 필욘 X
2번은 1~2번, 1번은 1번에만 도킹 가능하므로 그 자리를 3번이 가져가면 비효율적
→ 3번 비행기가 도착한다면 3번 게이트에 도킹 시도, 2번이 도착하면 일단 2번에 도킹 시도,,
서로소 집합 알고리즘
중복된 번호의 비행기가 도착할 수도 있으므로, 도착한 비행기의 도킹 여부 파악이 필요
비행기가 도착할 때마다 게이트의 도킹 가능 여부를 일일이 2중 반복문으로 체크해 보기엔,, 게이트와 비행기 수가 각각 100,000개로 시간 초과 발생 우려
서로소 집합 알고리즘을 활용하여 특정 게이트에 도킹을 시도할 때 도킹 가능 여부 및 불가능 하다면 다음 목적지 게이트를 지시하자!
EX
게이트 수 4, 총 3대의 비행기 (4, 1, 1), 도킹 횟수 0
게이트의 초기 부모 테이블
부모
0
1
2
3
4
게이트
0
1
2
3
4
4번 비행기가 4번 게이트로 진입
부모
0
1
2
3
3
게이트
0
1
2
3
4
find 연산을 통해 얻은 부모가 게이트 번호와 같다면 도킹 가능 : 4 == 4, 도킹횟수 +1
4번 게이트가 차 있으므로 앞으로 4번 비행기가 들어오면 3번에 도킹 시도 지시가 필요
→ union 연산을 통해 4번 게이트의 부모를 4 - 1 = 3번으로 설정
1번 비행기가 1번 게이트로 진입
부모
0
0
2
3
3
게이트
0
1
2
3
4
find 연산을 통해 얻은 부모가 게이트 번호와 같다면 도킹 가능 : 1 == 1, 도킹횟수 +1
1번 게이트가 차 있으므로 앞으로 1번 비행기가 들어오면 0번에 도킹 시도 지시가 필요
→ union 연산을 통해 1번 게이트의 부모를 0번으로 설정
1번 비행기가 1번 게이트로 진입
현재 1번 게이트의 부모가 0번이므로 0번게이트로 가야 함.
→ 0번은 존재하지 않는 게이트, 즉 더 이상 도킹 불가
최대 도킹 가능 횟수는 2
→ 이러한 방식을 경로 단축 기법이라 함. 게이트의 도킹 가능 여부를 최대 O(N)의 연산횟수에서 O(1)로 단축 가능
풀이

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.