n + 1 카드게임
2024 카카오 윈터 인턴쉽 문제가 오픈되어 풀어보았다.
문제 설명
- 1 ~ n 까지의 숫자가 적혀있는 카드가 무작위로 석여있다.
- 처음에는 카드 n / 3 장을 가진다.
- 라운드가 시작될 때마다 2장을 뽑고 1장에 1개 코인을 사용해서 뽑은 카드를 사용할 수 있다.
- 라운드마다 n + 1 의 합이 되는 카드 2장을 내야한다.
- 그러지 못하면 게임은 종료된다.
최대 라운드 수를 구해라
흐름 파악
흐름 파악을 위해 꼬리에 꼬리를 무는 방식으로 접근하려한다.
최대 라운드 수를 어떻게 구하지?
카드의 수는 중복이 없으니까 각 카드별로 짝을 이룰 수 있는 수는 정해져있어
조합이 될 때마다 해당 조합을 내고 다음 라운드를 진행하면서 최대 라운드 수를 구하면 되겠네
시행착오
BFS, DFS 로 접근하려고 했는데 시간초과가 났다.
코드를 작성하고 보니 최대를 구하다보니 조기 종료 조건이 없었다.
해봤자 현재 라운드 + (남은 카드 수) / 2 < 지금까지 최대 라운드 정도인데 이 조건 또한 도움이 되지 않는다.
저 조건에 해당되기 한참 전 depth 부터 너무 많은 경우의 수가 발생하기 때문이다.
BFS, DFS 를 선택했던 이유는 모든 경우의 수를 계산하지 않고는 최대 라운드 수를 확정할 없다고 생각했기 떄문이다.
그렇지만 달리 생각해보면 뽑은 카드를 해당 라운드에서 사용하지 못해도 저장하고 있다가 필요한 숫자가 나올 때 coin 을 사용해서 사용한다면 코인을 적재적소에 사용한 것이다. 이러한 컨셉으로 라운드를 계속 진행시키면서 3가지 로직을 진행한다.
- 현재 가지고 있는 카드로 짝을 이룰 수 있는지 확인한다.
- 현재 라운드에 뽑은 카드 2장을 포함해서 이전에 가질 수 있는 카드 목록 중 1장을 사용해서 짝을 이룰 수 있는지 확인한다.
- 현재 라운드에 뽑은 카드 2장을 포함해서 이전에 가질 수 있는 카드 목록 중 2장을 사용해서 짝을 이룰 수 있는지 확인한다.
전체 코드
import random
from collections import deque
def solution(coin, cards):
answer = 1
hands = cards[0:len(cards) // 3]
remain_cards = deque(cards[len(cards) // 3:])
able_remain_cards = []
cur_round = 0
hands_dict = {v: True for v in hands}
while True:
cur_round += 1
if not hands and not remain_cards:
break
if remain_cards:
able_remain_cards.append(remain_cards.popleft())
if remain_cards:
able_remain_cards.append(remain_cards.popleft())
pair = []
for c in hands:
if (len(cards) + 1) - c in hands_dict:
pair.append(c)
pair.append((len(cards) + 1) - c)
break
if pair:
hands.remove(pair[0])
hands.remove(pair[1])
del hands_dict[pair[0]]
del hands_dict[pair[1]]
continue
if coin == 0:
break
for able_card in able_remain_cards:
if (len(cards) + 1) - able_card in hands_dict:
pair.append((len(cards) + 1) - able_card)
pair.append(able_card)
break
if pair:
hands.remove(pair[0])
able_remain_cards.remove(pair[1])
coin -= 1
del hands_dict[pair[0]]
continue
if coin == 1:
break
able_remain_card_dict = {v: True for v in able_remain_cards}
for c in able_remain_cards:
if (len(cards) + 1) - c in able_remain_card_dict:
pair.append(c)
pair.append((len(cards) + 1) - c)
break
if pair:
able_remain_cards.remove(pair[0])
able_remain_cards.remove(pair[1])
coin -= 2
continue
break
return cur_round
print(solution(1000, random.sample([i for i in range(1000)], 1000)), 500)
print(solution(4, [3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4]), 5)
print(solution(3, [1, 2, 3, 4, 5, 8, 6, 7, 9, 10, 11, 12]), 2)
print(solution(2, [5, 8, 1, 2, 9, 4, 12, 11, 3, 10, 6, 7]), 4)
print(solution(10, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]), 1)
