Baekjoon 16566. 카드 게임 / Python

알고리즘 설명

1. 입력 처리:
   • N, M, K는 각각 카드의 총 개수, 빨간색 카드의 수, 카드 게임의 횟수를 나타냅니다.
   • pushed_h20는 철수가 선택한 M개의 빨간색 카드의 번호를 오름차순으로 정렬한 리스트입니다.
   • fe_h20는 철수가 게임에서 낼 카드의 번호를 나타내는 리스트입니다.
2. Union-Find 자료구조 초기화:
   • arr 리스트는 각 카드의 부모 노드를 저장합니다. 초기 상태에서 모든 카드의 부모는 자기 자신입니다.
3. Find 함수:
   • 주어진 카드의 최종 부모를 찾는 함수입니다. 경로 압축을 통해 효율성을 높입니다.
4. Sol 함수:
   • 카드의 부모를 통합하는 함수입니다. 이 함수는 find 함수에서 얻은 부모 노드를 통해 카드의 그룹을 연결합니다.
5. 이진 탐색:
   • bisect_right를 사용하여 fe_h20의 각 카드에 대해, pushed_h20에서 그 카드보다 큰 카드 중에서 가장 작은 카드의 인덱스를 찾습니다.
6. 출력:
   • pushed_h20에서 찾은 카드 번호를 출력합니다.

import sys
from bisect import bisect_right as br  # bisect_right: 이진 탐색으로 주어진 카드보다 큰 카드 중 가장 작은 카드의 인덱스를 찾는다.
input = sys.stdin.readline 

# 입력받은 값을 정수형으로 변환
n, m, k = map(int, input().split())  
# 빨간색 카드 번호를 입력받아 오름차순으로 정렬
pushed_h20 = sorted(list(map(int, input().split())))  
# 철수가 낼 카드의 번호를 입력받음
fe_h20 = list(map(int, input().split()))  

# Union-Find 자료구조를 위한 초기화
arr = list(range(m))  # 초기에는 각 카드의 부모는 자기 자신

# Find 함수: 경로 압축 기법을 사용하여 부모 노드를 찾는 함수
def find(x):
    if arr[x] != x:
        arr[x] = find(arr[x])  # 재귀적으로 부모를 찾으면서 경로 압축
    return arr[x]

# Sol 함수: 두 카드의 부모를 통합하는 함수
def sol(x, y):
    if y >= m:
        return  # y가 범위를 벗어나면 무시
    x = find(x)  # x의 부모 노드 찾기
    y = find(y)  # y의 부모 노드 찾기
    arr[x] = y  # x의 부모를 y로 설정하여 두 그룹을 연결

# 각 철수의 카드에 대해 민수가 낼 카드의 번호를 찾는 과정
for i in fe_h20:
    idx = br(pushed_h20, i)  # i보다 큰 카드 중에서 가장 작은 카드의 인덱스 찾기
    idx = find(idx)  # 해당 인덱스의 실제 부모를 찾기
    print(pushed_h20[idx])  # 해당 카드의 번호를 출력
    arr[idx] += 1  # 해당 카드의 부모를 수정하여 다음 큰 카드를 찾기 위해 카운트 증가