Chap 18. 그래프이론 - Q42. 탑승구

@mildsalmon·2021-11-30 10:11

1. 탑승구

난이도
- 중
풀이 시간
- 50분
시간 제한
- 1초
메모리 제한
- 128MB
출처
- CCC

A. 📜 문제

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

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

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

a. 입력 조건

첫째 줄에는 탑승구의 수 G (1 <= G <= 100,000)가 주어진다.
둘째 줄에는 비행기의 수 P (1 <= P <= 100,000)가 주어진다.
다음 P개의 줄에는 각 비행기가 도킹할 수 있는 탑승구의 정보 $g_i$ (1 <= $g_i$ <= G)가 주어진다. 이는 i번째 비행기가 1번부터 $g_i$번째 (1 <= $g_i$ <= G) 탑승구 중 하나에 도킹할 수 있다는 의미이다.

b. 출력 조건

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

c. 테스트 케이스

입력 예시
```
4
3
4
1
1
```
```
4
6
2
2
3
3
4
4
```
출력 예시
```
2
```
```
3
```

B. 💡 내 답안

a. 😅 1차 시도 (실패 / union-find로 구현하지 못함)


g = int(input())
p = int(input())

boarding_gate = []

for _ in range(p):
    boarding_gate.append(int(input()))

docking = [i for i in range(g+1)]
count = 0

for b_g in boarding_gate:
    while docking[b_g] != b_g:
        b_g -= 1

        if b_g == 0:
            b_g = 1
            break

    if docking[b_g] == b_g:
        docking[b_g] = 0
        count += 1
    elif docking[b_g] == 0:
        break

print(count)

b. 😊 2차 시도 (성공)


"""
Date    : 2021.11.30
Update  : 2021.11.30
Source  : Q42_탑승구.py
Purpose : union-find 알고리즘 적용하여 해결.
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""

def find_parent(parent, node):
    if parent[node] != node:
        parent[node] = find_parent(parent, parent[node])

    return parent[node]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    elif a > b:
        parent[a] = b

g = int(input())
p = int(input())

boarding_gate = []

for _ in range(p):
    boarding_gate.append(int(input()))

docking = [i for i in range(g+1)]
count = 0

for b_g in boarding_gate:
    parent = find_parent(docking, b_g)

    if parent == 0:
        break
    else:
        union_parent(docking, parent, parent-1)
        count += 1

print(count)