[프로그래머스 문제풀이]2024 KAKAO WINTER INTERNSHIP n+1 카드게임

문제흐름을 살펴보면 카드가 2장 주어졌을 때, 한 장도 가지지 않을 것인지, 한 장을 가질 것인지, 두 장을 가질 것 인지를 결정해야 한다.

여기서 포인트는 카드를 뽑을 것인가는 당장 정하지 않는다는 것이다.

지금 당장 n+1을 만들 수 있는 카드 조합이 있다면, 카드를 뽑지 않고, 카드 더미에 쌓아두는 것이다.

당장 카드를 뽑지 않아도 나중에 필요할 때 coin을 사용해서 n+1 카드를 만들 수 있는 것이다.

 

따라서 전체적인 흐름은 아래와 같다.

 

1. 카드를 카드 더미에 쌓는다.

2. n+1 해결하기

   1. 수중에 있는 카드로 n+1을 만들 수 있다면, 다음 카드 뽑기

   2. coin을 사용해야 한다.

    2-1. coin 없다면 게임 끝

    2-2. coin 한 개를 사용해서 (수중에 카드 한 장 +  카드 더미에서 카드 한 장)= n+1을 만들 수 있다면 coin 한 개를 소모해서 n + 1을 만든다.

   2-3. coin 두 개  이상 없다면 게임 끝

   2-4. coin 두 개를 사용해서 (카드 더미에서 카드 두 장) = n+1을 만든다.

 

이를 코드로 작성해 보자.

 

def remove_card(cards,n):
    f_n, s_n = -1, -1
    ret = []
    for card in cards:
        if n-card in cards:
            f_n , s_n = card, n-card
    for card in cards:
        if card != f_n and card != s_n:
            ret.append(card)
    return ret

def can_make(hands,n):
    for h in hands:
        if n-h in hands:
            return True
    return False

def can_make_available(hands,available_card,n):
    for hand in hands:
        if n-hand in available_card:
            return True
    return False

def remove_make_available(hands,available_card,n):
    for hand in hands:
        if n-hand in available_card:
            hands.remove(hand)
            available_card.remove(n-hand)
            return 
            
def solution(coin, cards):
    available_card = []
    n = len(cards)+1
    hands = cards[:len(cards)//3]
    cards = cards[len(cards)//3:]
    for idx in range(len(cards)//2):
        available_card.append(cards[idx*2])
        available_card.append(cards[idx*2+1])
        if can_make(hands,n):
            hands = remove_card(hands,n)
            continue
        if coin<=0:
            return idx+1
        if can_make_available(hands,available_card,n):
            remove_make_available(hands,available_card,n)
            coin-=1
            continue
        if coin>1 and can_make(hands+available_card,n):
            available_card = remove_card(available_card,n)
            coin-=2
            continue
        return idx+1
    return idx+2

 

 

n+1을 만들 수 없는 경우를 생각하기보다 n+1을 만들 수 있는 경우만 찾고 나머지는 만들 수 없다고 판단하였다.

문제를 풀기 위해선 특정 알고리즘을 사용한다기보다 카드 더미를 사용하여 지금 당장 카드를 뽑지 않아도 된다.라는 포인트를 파악하는 게 핵심인 것 같다.