[이코테] 탑승구

문제

공항에는 G개의 탑승구가 있으며, 각각의 탑승구는 1번부터 G번까지의 번호로 구분됩니다.

공항에는 P개의 비행기가 차례대로 도착할 예정이며, i번째 비행기를 1번부터 $g_i$번째(1 $\leq$ $g_i\(\leq\)G$) 탑승구 중 하나에 영구적으로 도킹해야 합니다. 이때, 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있습니다.

또한 P개의 비행기를 순서대로 도킹하다가 만약에 어떠한 탑승구에도 도킹할 수 없는 비행기가 나오는 경우, 그 시점에서 공항의 운행을 중지합니다. 공항의 관리자는 최대한 많은 비행기를 공항에 도킹하고자 합니다. 비행기를 최대 몇 대 도킹할 수 있는지를 출력하는 프로그램을 작성하세요.

입력 조건

첫째 줄에는 탑승구의 G(1 $\leq$ G $\leq$ 100,000)가 주어집니다.

둘째 줄네는 비행기의 수 P(1 $\leq$ P $\leq$ 100,000)가 주어집니다.

다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 $g_i$(1 $\leq$ $g_i\(\leq\)G$) 가 주어집니다. 이는 i번째 비행기가 1번부터 $g_i$(1 $\leq$ $g_i\(\leq\)G$) 탑승구 중 하나에 도킹할 수 있다는 의미입니다.

출력 조건

첫째 줄에 도킹할 수 있는 비행기의 최대 개수를 출력합니다.

입출력 예

Example 1:

Input: 
4
3
4
1
1
Output: 
2

풀이과정

내 풀이

풀이법이 떠오르지 않아서 책 풀이 설명만 보고 코드를 작성하였다.

# 서로소 집합 알고리즘 정의
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a
# 탑승구의 수
g = int(input())

# 비행기의 수
p = int (input())

# 루트 노드 정의
parent = [0] * (g + 1)
for i in range(g + 1):
    parent[i] = i

# 결과 계산 및 출력
result = 0
for _ in range(p):
    gi = int(input())
    union = False
    for j in range(gi, 0, -1):
        if parent[j] == j:
            union_parent(parent, j-1, j)
            result += 1
            union = True
            break
    if union == False:
        break

print(result)

책 풀이

이 문제는 서로소 집합 알고리즘을 이용하면 효율적으로 해결할 수 있다. 각 탑승구를 서로 다른 집합으로 나타낸다고 해보자. 전체 탑승구가 4개(G = 4)일 때, 다음과 같이 그릴 수 있다. 초기 상태는 모두 루트 노드로 자기 자신을 가리키고 있다고 가정한다. 엄밀히 말하면 0번 탑승구는 존재하지 않지만, 문제 해결을 위해 0번 탑승구도 그려주도록 하자.

이때 비행기가 순서대로 들어오면 차례대로 도킹을 수행해야 하는데, 가능한 큰 번호의 탑승구로 도킹을 수행한다고 가정해보자. 이때 우리는 도킹하는 과정을 탑승구 간 합집합(union) 연산으로 이해할 수 있다. 새롭게 비행기가 도킹이 되면, 해당 집합을 바로 왼쪽에 있는 집합과 합친다. 단, 집합의 룬트가 0이면, 더 이상 도킹이 불가능한 것으로 판단한다. 이러한 과정을 통해 문제를 해결할 수 있다. 예를 들어 문제의 ‘입력 예시 2’대로 비행기 정보가 입력된다고 하면, 다음과 같이 처리할 수 있다.

1. 비행기 1

첫 번째 비행기는 1부터 2까지의 탑승구 중 하나에 도킹할 수 있다. 따라서 2번 노드를 확인하는데, 현재 2번 노드의 루트는 2이다. 그러므로, 2번 노드와 1번 노드에 대하여 합집합 연산을 수행한다.

2. 비행기 2

두 번째 비행기는 1부터 2까지의 탑승구 중 하나에 도킹할 수 있다. 따라서 2번 노드를 확인하는데 현재 2번 노드의 루트는 1이다. 그러므로, 1번 노드와 0번 노드에 대하여 합집합 연산을 수행한다.

3. 비행기 3

세 번째 비행기는 1부터 3까지의 탑승구 중 하나에 도킹할 수 있다. 따라서 3번 노드를 확인하는데, 현재 3번 노드의 루트는 3이다. 그러므로, 3번 노드와 2번 노드에 대하여 합집합 연산을 수행한다.

4. 비행기 4

네 번째 비행기는 1부터 3까지의 탑승구 중 하나에 도킹할 수 있다. 따라서 3번 노드를 확인하는데, 현재 3번 노드의 루트는 0이다. 루트가 0이라는 점에서 더 이상 도킹을 할 수 없다라는 의미이므로, 여기에서 마친다. 지금까지 총 3개의 비행기가 도킹이 되었으므로, 3을 출력하면 정답이다.

따라서 이 문제는 이처럼 서로소 집합 자료구조를 이용하여 해결할 수 있다. 이러한 아이디어를 소스코드로 구하면 다음과 같다.

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b
        
# 탑승구의 개수 입력받기
g = int(input())
# 비행기의 개수 입력받기
p = int(input())

parent = [0] * (g + 1) # 부모 테이블 초기화

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, g + 1):
    parent[i] = i
    
result = 0
for _ in range(p):
    data = find_parent(parent, int(input())) # 현재 비행기의 탑승구의 루트 확인
    if data == 0: # 현재 루트가 0이라면, 종료
        break
    union_parent(parent, data, data - 1) # 그렇지 않다면 바로 왼쪽의 집합과 합치기
    result += 1
    
print(result)