Jin의 일상

www.acmicpc.net/problem/10775

문제 설명

1. G개의 게이트 수가 주어진다.

2. P개의 비행기는 순차대로 날아오며, 비행기마다 i값을 갖는다.

3. 비행기는 1~G(i) 게이트 중 하나에 주차된다.

 - 주차될 수 없다면, 더 이상 비행기가 공항으로 날아오지 않는다.

4. 가장 많은 비행기가 주차됐을 때 수는?

조건 범위

G (1 ≤ G ≤ 10^5)

P (1 ≤ P ≤ 10^5)

gi (1 ≤ gi ≤ G)

특이사항

반복문으로 이 문제를 풀 경우, 최대 10^5 * O(10^5)가 걸립니다. (10,000,000,000)

파이썬이 1초에 50,000,000 정도 계산한다고 가정했을 때, 반복문으로 풀면 안됩니다.

따라서 이 문제는 "유니온-파인드"를 이용해서 해결해야 합니다.

알고리즘

총 6대의 비행기가 각 [4, 3, 2, 1, 4]의 값을 가지고 게이트에 날아온다고 가정하겠습니다.

1. 리스트를 만듭니다. 리스트 명은 gates로 정의하겠습니다. 또한, 각 인덱스의 값은 parent를 의미합니다.

 - 인덱스와 parent가 같다면, 주차장이 빈 상태임을 의미합니다.

 - 인덱스와 parent가 다르다면, 이미 비행기가 주차된 상태를 의미합니다.

2. i가 4인 비행기가 날아옵니다.

(2-1) gates의 4번 인덱스의 부모 노드를 확인합니다.

 - 부모노드는 4이므로, 해당 게이트에 주차되지 않은 상태입니다. 비행기를 4번 게이트에 주차시킵니다. (cnt 1 증가)

(2-2) 4번 게이트가 주차됐으므로, 한 칸 앞에 위치한 게이트의 부모노드를 값으로 수정합니다.

3. i가 3인 비행기가 날아옵니다.

 - 알고리즘 2번과 동일한 상황이므로, 3번 게이터에 주차(cnt 1 증가)시키고 앞에 위치한 부모노드 값으로 수정합니다.

4. i가 2인 비행기가 날아옵니다.

 - 알고리즘 2번과 동일한 상황이므로, 2번 게이터에 주차(cnt 1 증가)시키고 앞에 위치한 부모노드 값으로 수정합니다.

5. i가 1인 비행기가 날아옵니다.

 - 알고리즘 2번과 동일한 상황이므로, 1번 게이터에 주차(cnt 1 증가)시키고 앞에 위치한 부모노드 값으로 수정합니다.

6. i가 4인 비행기가 날아옵니다.

- gates의 4번 인덱스의 부모 노드를 확인합니다.

4번 인덱스의 부모노드는 자신의 값과 다릅니다. 즉, 4번 인덱스에는 비행기가 주차되어 있습니다.

따라서 4번 인덱스의 부모 노드로 이동합니다. 조금 전과 같은 상황이 연쇄적으로 반복됩니다.

재귀적으로 호출한 결과는 역순으로 리턴됩니다.

따라서 지나온 경로의 gates 인덱스는 부모 노드로 수정됩니다. 

참고로 지나온 경로를 이렇게 수정하는 테크닉을 "경로 단축"이라고 합니다.

경로 단축 테크닉을 사용하면 다음 번에 다시 i가 4인 비행기가 날아왔을 때

이번과 같이 O(N)경로를 지나지 않고 O(1)로 리턴할 수 있습니다.

방금 과정에서 4번 비행기가 날아왔을 때 0을 리턴했습니다.

이는 모든 게이트가 꽉 찼음을 의미합니다. 따라서 알고리즘을 종료합니다.

코드

import sys

sys.stdin = open("C:/Users/JIn/PycharmProjects/coding_Test/input.txt", "rt")


def find(n):
    if gates[n] == n:
        return n
    else:
        gates[n] = find(gates[n])
        return gates[n]


def union(a, b):
    x = find(a)
    y = find(b)
    gates[x] = y
    return

if __name__ == "__main__":
    numGate = int(input())
    numPlane = int(input())
    gates = list(range(numGate + 1))

    cnt = 0
    for _ in range(numPlane):
        gate = int(input())
        parent = find(gate)
        if parent == 0:
            break
        union(parent, parent-1)
        cnt += 1
    print(cnt)