[백준 16566번] 파이썬 - 카드 게임

백준 16566_카드 게임

시간 제한 1.2초, 메모리 제한 512MB

# 조건

• 철수와 민수는 카드 게임을 즐겨한다. 이 카드 게임의 규칙은 다음과 같다.
  1. N개의 빨간색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 M개의 카드를 고른다.
  2. N개의 파란색 카드가 있다. 각각의 카드는 순서대로 1부터 N까지 번호가 매겨져 있다. 이 중에서 빨간색에서 고른 번호와 같은 파란색 카드 M개를 고른다.
  3. 철수는 빨간색 카드를 가지고 민수는 파란색 카드를 가진다.
  4. 철수와 민수는 고른 카드 중에 1장을 뒤집어진 상태로 낸다. 그리고 카드를 다시 뒤집어서 번호가 큰 사람이 이긴다. 이 동작을 K번 해서 더 많이 이긴 사람이 최종적으로 승리한다. 한 번 낸 카드는 반드시 버려야 한다.
• 철수는 뛰어난 마술사이기 때문에 본인이 낼 카드를 마음대로 조작할 수 있다.
  • 즉, 카드를 버리고 민수 몰래 다시 들고 온다거나 민수한테 없는 카드를 내기도 한다.
• 민수는 뛰어난 심리학자이기 때문에 철수가 낼 카드를 알아낼 수 있다. 그래서 민수는 철수가 낼 카드보다 큰 카드가 있다면 그 카드들 중 가장 작은 카드를 내기로 했다.
• K번 동안 철수가 낼 카드가 입력으로 주어진다.
• 그렇다면 민수가 어떤 카드를 낼지 출력하라. 단, 민수가 카드를 내지 못하는 경우는 없다고 가정한다.

입력

• 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000))
• 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 다르다.
• 다음 줄에 K개의 자연수가 주어진다. i번째 수는 철수가 i번째로 내는 카드의 번호이다.
• 철수가 내는 카드 역시 1 이상 N 이하이다.

# 접근 방법

pypy 통과

• 이진탐색을 이용하기 위하여 bisect 라이브러리를 사용해주었다.
• 또한, cards 길이만큼의 dp 배열을 만들어준 후 철수가 낸 카드를 순회한다.
• 해당 카드를 bisect_right를 이용하여 들어갈 idx를 구하고 cards 배열의 idx값을 출력해준다.
  • 이 때, 이미 낸 적이 있는 카드라면 idx+1부터 M까지 dp배열을 탐색하며 내지 않은 카드 중 가장 작은 카드의 인덱스를 찾아준다.
  • 낸 적이 없다면 바로 출력해주고 1로 변경해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from bisect import bisect_right  

N, M, K = map(int, input().split())  
cards = [*map(int, input().split())]  
chulsoo = [*map(int, input().split())]  
dp = [0] * M  
cards.sort()  
for i in chulsoo:  
    idx = bisect_right(cards, i)  
    if dp[idx]:  
        for j in range(idx+1, M):  
            if not dp[j]:  
                print(cards[j])  
                dp[j] = 1  
                break  
    else:  
        print(cards[idx])  
        dp[idx] = 1

python3 통과

• 위의 방법에서 시간을 더 줄여주기 위해서 고민을 하였다.

for j in range(idx+1, M):  
            if not dp[j]:  
                print(cards[j])  
                dp[j] = 1  
                break 

• 위와 같이 이미 사용한 카드를 제외하고 가장 작은 카드를 찾는 부분 로직을 분리집합을 이용하여 구현해주었다.
• 즉, 2 3 4 5 7 8 9가 있을 때, 5가 사용되었다면 다음 7을 사용할 수 있도록 인덱스로 표시를 해주는 것이다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from bisect import bisect_right  


def find(x):  
    if x != parents[x]:  
        parents[x] = find(parents[x])  
    return parents[x]  

def union(x, y):  
    if y >= M:  
        return  
    x = find(x)  
    y = find(y)  
    parents[x] = y  

N, M, K = map(int, input().split())  
cards = [*map(int, input().split())]  
chulsoo = [*map(int, input().split())]  
parents = [i for i in range(M)]  
cards.sort()  
for i in chulsoo:  
    idx = bisect_right(cards, i)  
    idx = find(idx)  
    print(cards[idx])  
    union(idx, idx+1)