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

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)

c. 🙄 회고

내 풀이

  • 구현으로 풀었다.

반성

  • union-find 파트에 있는 문제인데도, 어떻게 알고리즘을 적용해야하는지 생각나지 않았다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

비행기는 1번 ~ $g_i$번까지 도킹할 수 있다. 그러니 가능하면 마지막 번호에 도킹해야한다. 도킹하려는 자리에 다른 비행기가 있다면, 앞 번호에 도킹해야한다.

현재 번호에 도킹했다면, 비행기는 바로 앞 번호와 union해준다. 이를 통해 현재 번호는 도킹이 불가능하다는 것을 알려준다. 만약 앞 번호(부모)가 0이라면, 더 이상 도킹할 위치가 없는 것이기 때문에 공항 운행을 중지한다.

![[Chap 18. 그래프이론 - Q42. 탑승구.png]]

a. 책 답안

python-for-coding-test/2.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

이 글이 도움이 되었나요?

0 minutes ago
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.