https://school.programmers.co.kr/learn/courses/30/lessons/258707
문제 파악
이 문제는 규칙이 좀 많아 예시를 보며 흐름을 파악해보겠다.
coin과 cards가 있는데
coin을 4, cards 를 [3,6,7,2,1,10,5,9,8,12,11,4] 이렇게 받았다고 해보겠다.
처음 플레이어는 카드 개수의 나누기 3 한만큼 카드를 앞에서부터 가진다.
즉 hand = [3,6,7,2] 가 첫 핸드에 들어온다.
- 라운드가 시작될 때 카드를 두 장 뽑는다. => 1,10
(이때 카드 뭉치에 남은 카드가 없다면 게임을 종료한다.) - 뽑은 카드는 카드 한 장당 동전을 하나 소모하면 가질 수 있고, 소모하지 않으면 버릴 수 있다.
- 가질지 버릴지 정했다면 그 다음으로, 카드에 적힌 수의 합이 n+1 이 되도록 카드를 두 장 내야 한다. 즉 이 경우 13의 합을 가지는 카드 두장을 내야 다음 라운드로 진행할 수 있다. 만약 카드 두 장을 낼 수 없다면 게임이 즉시 종료된다.
1과 10 을 coin 2개를 소모해서 가졌다면
hand = [3,6,7,2,1,10] , coin = 2 가 된다.
n+1 = 13이므로 13이 될 수 있는 수 3과 10을 내고 다음 라운드로 진행한다.
-
2라운드
hand = [6,7,2,1] , cards = [5,9,8,12,11,4], coin = 2
이번엔 5,9 인데 5,9를 받아도 13을 만들 수 없기 때문에 버린다.
6과7을 내고 13을 만들고 3라운드로 넘어간다. -
3라운드
hand = [2,1], cards = [8,12,11,4], coin =2
8, 12 / 12를 받으면 1과 함께 13을 만들 수 있으므로 coin 1개만 내고 12를 받는다.
1과 12를 내고 다음라운드로 간다. -
4라운드
hand = [2], card = [11,4], coin = 1
11,4 중 11을 받으면 13을 낼 수 있다.
11을 받고, 2,12를 내고 다음라운드로 간다. -
5라운드
hand = [], card = [], coin = 0
이때 카드 뭉치에서 2장 뽑아야하는데 남은 카드가 없기에 게임이 종료되며
라운드 수인 5를 return 하면 답이다.
해결 아이디어
https://xkdls19.tistory.com/305 를 참고해 공부했다.
stack에서 2장씩 뽑는데, 그때 바로 hand에 있는 카드와 매치되면 바로 핸드에 추가해주고, 아니면 temp라는 임시 리스트에 넣어준다.
그리고 그 temp 리스트에 누적시키며 카드를 모으고,
코인을 0개 쓰는 우선순위에서 2개쓰는 우선순위로 올라가며 확인해보는 로직이었다.
hand: 시작 손패
temp: 보드에 깔려 있지만 아직 안 산 카드들의 집합(라운드가 지나도 누적)
라운드마다 공개된 2장에 대해:
손패에 파트너가 이미 있으면 → 1코인으로 즉시 구매해 손패로 편입(손패 강화)
아니면 보드(temp)에 누적
그 다음, 통과 시도 우선순위:
hand-hand(0코인): 손패-손패로 n+1 완성
hand-temp(1코인): 손패 카드 + 보드의 짝 1장 구매
temp-temp(2코인): 보드의 두 장을 2코인으로 구매
→ 모두 실패 시 종료
직관: 0 → 1 → 2코인 순서로만 시도하면 같은 코인으로 더 많은 라운드를 산다.
temp를 누적해 두면 당장 못 써도 나중에 HB/BB에서 쓸 가능성이 계속 커진다.
def solution(coin, cards):
answer = 1 # 라운드 수, 첫 라운드 = 1
n = len(cards)
hand = set(cards[:n//3]) # cards에 앞에서부터 1/3
stack = cards[n//3:] # cards에 앞에서부터 1/3 뒷부분
temp = set()
for i in range(len(stack) // 2): # stack에서 한번에 두장씩 뽑으니 len(stack)//2 번 반복
for x in stack[2*i:2*i+2]: # 2*i와 2*i+1 두장씩 뽑음
if n+1-x in hand and coin: # x의 짝 = n+1-x , 그리고 coin이 있으면 구매
coin -= 1
hand.add(x)
else: # 아니면 temp에
temp.add(x)
check1 = False # 손패 - 손패 쌍
for x in hand:
if n+1-x in hand:
hand.remove(x)
hand.remove(n+1-x)
answer += 1
check1 = True
break
# 손패 - temp 매칭
if not check1: # check1이 False라면
check2 = False
for x in hand:
if n+1-x in temp and coin:
coin -= 1
answer += 1
hand.remove(x)
temp.remove(n+1-x)
check2 = True
break
if not check2:
for x in temp: # temp 내에서 매칭
if n+1-x in temp and coin >= 2:
coin -= 2
answer += 1
temp.remove(x)
temp.remove(n+1-x)
break
else:
return answer
return answer