문제 요약
1부터 n까지의 카드가 한 장씩 있고, 카드를 뽑는 순서가 cards로 주어진다.
처음에는 n / 3장의 카드를 가지고 시작한다.
이후 매 라운드마다 카드 2장을 뽑고, 다음 라운드로 넘어가기 위해서는 합이 n + 1이 되는 카드 2장을 내야 한다.
라운드에서 새로 뽑은 카드는 카드 한 장당 동전 1개를 사용해야 가질 수 있다.
게임에서 도달할 수 있는 최대 라운드 수를 구해야 한다.
핵심 아이디어
합이 n + 1이 되는 카드 쌍만 의미가 있다.
예를 들어 n = 12라면 다음과 같은 쌍이 필요하다.
1 + 12
2 + 11
3 + 10
4 + 9
5 + 8
6 + 7각 카드는 정확히 하나의 짝만 가진다.
따라서 매 라운드에서 가능한 쌍을 찾되, 동전을 적게 쓰는 쌍부터 사용하는 것이 유리하다.
카드 집합 나누기
카드는 두 종류로 관리한다.
1. hand
처음부터 가지고 있던 카드 또는 동전을 사용해서 실제로 가진 카드다.
2. candidate
라운드에서 뽑았지만 아직 동전을 사용하지 않은 카드다.
문제에서는 뽑은 카드를 바로 가지거나 버린다고 되어 있지만, 풀이에서는 뽑힌 카드를 candidate에 보관해둔다.
이는 실제로 카드를 계속 들고 있는 것이 아니라, 나중에 필요할 때 동전을 사용해서 가져올 수 있는 후보로 생각하는 것이다.
쌍을 고르는 우선순위
다음 라운드로 넘어가기 위해 합이 n + 1인 카드 두 장을 내야 한다.
가능한 쌍은 동전 사용량에 따라 세 가지다.
1. hand + hand
이미 가지고 있는 카드 두 장으로 쌍을 만든다.
필요한 동전 수는 0개다.
2. hand + candidate
가지고 있는 카드 한 장과, 뽑힌 후보 카드 한 장으로 쌍을 만든다.
후보 카드 한 장을 가져와야 하므로 동전 1개가 필요하다.
3. candidate + candidate
후보 카드 두 장으로 쌍을 만든다.
두 장 모두 가져와야 하므로 동전 2개가 필요하다.
동전을 아껴야 더 많은 라운드를 진행할 수 있으므로 다음 순서로 확인한다.
hand + hand
hand + candidate
candidate + candidate풀이 과정
1. 초기 카드 설정
처음 n / 3장의 카드를 hand에 넣는다.
hand = set(cards[:n // 3])그 이후 카드들은 라운드마다 2장씩 확인한다.
2. 매 라운드마다 카드 2장 뽑기
candidate.add(cards[i])
candidate.add(cards[i + 1])새로 뽑은 카드는 일단 후보 카드 집합에 넣는다.
3. 가능한 쌍 찾기
합이 n + 1이 되는 쌍을 다음 순서로 찾는다.
hand안에서 쌍 찾기hand와candidate사이에서 쌍 찾기candidate안에서 쌍 찾기
쌍을 만들 수 있으면 해당 카드들을 제거하고 다음 라운드로 넘어간다.
쌍을 만들 수 없으면 현재 라운드에서 게임이 종료된다.
Python 코드
def solution(coin, cards):
n = len(cards)
target = n + 1
hand = set(cards[:n // 3])
candidate = set()
round_count = 1
def remove_pair_from_same(card_set):
for card in list(card_set):
pair = target - card
if pair in card_set:
card_set.remove(card)
card_set.remove(pair)
return True
return False
def remove_pair_from_each(left_set, right_set):
for card in list(left_set):
pair = target - card
if pair in right_set:
left_set.remove(card)
right_set.remove(pair)
return True
return False
for i in range(n // 3, n, 2):
candidate.add(cards[i])
candidate.add(cards[i + 1])
if remove_pair_from_same(hand):
round_count += 1
continue
if coin >= 1 and remove_pair_from_each(hand, candidate):
coin -= 1
round_count += 1
continue
if coin >= 2 and remove_pair_from_same(candidate):
coin -= 2
round_count += 1
continue
break
return round_count코드 설명
목표 합
target = n + 1각 라운드에서 내야 하는 카드 두 장의 합이다.
초기 손패
hand = set(cards[:n // 3])처음에 뽑는 n / 3장의 카드는 동전 없이 모두 가진다.
빠르게 짝 카드를 찾기 위해 set으로 관리한다.
후보 카드
candidate = set()라운드마다 새로 뽑히는 카드를 저장한다.
이 카드는 아직 동전을 사용해 가진 카드는 아니지만, 필요할 때 동전을 내고 사용할 수 있는 카드로 본다.
같은 집합에서 쌍 찾기
def remove_pair_from_same(card_set):하나의 집합 안에서 합이 target이 되는 두 카드를 찾는다.
찾으면 두 카드를 제거하고 True를 반환한다.
서로 다른 집합에서 쌍 찾기
def remove_pair_from_each(left_set, right_set):한 장은 hand, 한 장은 candidate에서 사용하는 경우를 처리한다.
후보 카드 한 장을 가져와야 하므로 이 함수를 사용할 때는 동전 1개를 차감한다.
라운드 진행
for i in range(n // 3, n, 2):초기 카드 이후부터 2장씩 뽑는다.
쌍을 만들 수 있으면 round_count를 1 증가시킨다.
쌍을 만들 수 없다면 현재 라운드에서 종료되므로 반복을 멈춘다.
왜 동전을 적게 쓰는 쌍부터 고를까?
카드마다 합이 n + 1이 되는 짝은 하나뿐이다.
이미 가진 카드끼리 낼 수 있다면 동전을 쓸 이유가 없다.
동전을 덜 쓰는 선택을 먼저 해야 이후 라운드에서 후보 카드를 가져올 수 있는 가능성이 커진다.
따라서 다음 순서가 최선이다.
0코인 쌍 → 1코인 쌍 → 2코인 쌍시간 복잡도
카드 수를 n이라고 하자.
각 라운드마다 집합을 순회해 쌍을 찾는다.
최악의 경우 단순 구현 기준 시간 복잡도는 다음과 같다.
O(n^2)프로그래머스 제한에서는 충분히 통과 가능한 방식이다.
공간 복잡도
hand와 candidate 집합에 카드를 저장한다.
O(n)정리
이 문제는 매 라운드마다 합이 n + 1이 되는 카드 쌍을 만들 수 있는지 확인하는 문제다.
핵심은 새로 뽑은 카드를 바로 구매했다고 생각하지 않고, 후보 카드로 보관하는 것이다.
그리고 매 라운드마다 다음 우선순위로 쌍을 찾는다.
hand + hand
hand + candidate
candidate + candidate이렇게 하면 동전을 최대한 아끼면서 더 많은 라운드까지 진행할 수 있다.
