[이것이 코딩테스트다] 탑승구

문제

• 1번 ~ G번까지의 G개의 탑승구에 P개의 비행기가 순서대로 도킹한다.
  • 1 <= G, P <= 100,000
• i 번째 비행기를 1번부터 $g_i$ 번째 탑승구 중 하나에 영구적으로 도킹해야 한다.
  • 각 비행기별 도킹 가능한 최대 탑승구 번호 정보가 주어진다.
• 다른 비행기가 도킹하지 않은 탑승구에만 도킹할 수 있다.
• 순서대로 도킹하다가 어떤 탑승구에도 도킹할 수 없는 비행기가 나오면 그 시점에서 공항 운행을 중지한다.
• 최대 몇 대의 비행기를 도킹할 수 있을까?

 

풀이 1

• 완전탐색
• 각 비행기별로 최대 탑승구 ~  1번 차례로 도킹 가능한지 확인하기
• 시간 복잡도 : O(N*N) => 불가능! 
• 테스트 케이스가 몇 개 없어서 확인 불가능 하지만 시간 초과에 걸릴 코드..

 

G = int(input())    # 탑승구 수
P = int(input())    # 비행기 수

q = []
for _ in range(P):
    q.append(int(input()))   # 도킹 가능한 최대 탑승구 번호

docking = set()     # 현재 도킹된 탑승구 번호
for x in q:
    
    finish = True   # 종료 조건 flag
    # 최대 탑승구 ~ 1번까지 차례로 도킹 가능한지 확인하기
    for i in reversed(range(1, x+1)):
        if i not in docking:
            docking.add(i)
            add = False
            break
    
    # 도킹 불가능하면 끝!
    if finish :
        break

print(len(docking))

 

풀이 2

• 유니온 파인드
• 시간 복잡도 : O(N) => 가능! 

# 부모 찾기
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 = [i for i in range(G+1)]    # 부모 테이블
answer = 0
for _ in range(P):
    # 도킹 가능한 탑숭구 번호 찾기
    x = find_parent(parent, int(input()))
    
    if  x == 0 :    # 도킹 불가능하면 끝!
        break
    union_parent(parent, x, x-1)    # 도킹 가능하면 앞 번호랑 합치기
    answer += 1

print(answer)

 

 

References

• 이것이 코딩테스트다 Q42