[99클럽/파이썬 챌린저/35일차] n + 1 카드게임

프로그래머스 n+1 카드게임 LV3

 

문제 설명
당신은 1~n 사이의 수가 적힌 카드가 하나씩 있는 카드 뭉치와 동전 coin개를 이용한 게임을 하려고 합니다. 카드 뭉치에서 카드를 뽑는 순서가 정해져 있으며, 게임은 다음과 같이 진행합니다. 처음에 카드 뭉치에서 카드 n/3장을 뽑아 모두 가집니다. (n은 6의 배수입니다.) 당신은 카드와 교환 가능한 동전 coin개를 가지고 있습니다. 게임은 1라운드부터 시작되며, 각 라운드가 시작할 때 카드를 두 장 뽑습니다. 카드 뭉치에 남은 카드가 없다면 게임을 종료합니다. 뽑은 카드는 카드 한 장당 동전 하나를 소모해 가지거나, 동전을 소모하지 않고 버릴 수 있습니다. 카드에 적힌 수의 합이 n+1이 되도록 카드 두 장을 내고 다음 라운드로 진행할 수 있습니다. 만약 카드 두 장을 낼 수 없다면 게임을 종료합니다.
처음에 가진 동전수를 나타내는 정수 coin과 카드를 뽑는 순서대로 카드에 적힌 수를 담은 1차원 정수 배열 cards가 매개변수로 주어질 때, 게임에서 도달 가능한 최대 라운드의 수를 return 하도록 solution 함수를 완성해 주세요.

제한사항
0 ≤ coin ≤ n
6 ≤ cards의 길이 = n < 1,000
cards [i]는 i+1번째로 뽑는 카드에 적힌 수를 나타냅니다.
1 ≤ cards [i] ≤ n
cards의 원소는 중복되지 않습니다.
n은 6의 배수입니다.

입출력 예

coin	cards	result
4	[3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4]	5
3	[1, 2, 3, 4, 5, 8, 6, 7, 9, 10, 11, 12]	2
2	[5, 8, 1, 2, 9, 4, 12, 11, 3, 10, 6, 7]	4
10	[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]	1

 

 

딕셔너리를 이용하여 풀이하였다.

 

가장 큰 문제가 된 부분이 카드를 뽑고 버리는 부분인데, 이 경우를 필요할 때까지 뒤로 미루는 방식으로 선택했다.

 

처음에 준 카드로 n+1을 만들 수 있는 개수를 구한다.

해당 개수로 더 이상 진행할 수 없다면 그동안 가질 수 있던 카드를 이용한다

 

코인 1개를 써서 만들 수 있다면 해당 건을 우선으로 한다.

코인 2개를 써서 만들 수 있다면 위의 경우가 불가능할 때만 딱 한 번 시도한다

 

 

def solution(coin, cards):
    
    cur_cards = {}
    can_card = {}
    n = len(cards)

    cnt = 0
    for index in range(n//3):
        cur_cards[cards[index]] = 0
    index = n//3

    
    for key in list(cur_cards.keys()):
        pair = n+1-key
        if pair in cur_cards:
            cnt += 1
            del cur_cards[pair]
            del cur_cards[key]

    answer = 0
    while index < n:
        answer += 1
        can_card[cards[index]] = 0
        index += 1
        if index < n:
            can_card[cards[index]] = 0
            index += 1
        else:
            return answer + 1
        
        if cnt > 0:
            cnt -= 1
            continue

        if coin <= 0: return answer

        
        for key in list(can_card.keys()):
            if coin <= 0: break
            pair = n+1-key
            if pair in cur_cards:
                coin -= 1
                cnt += 1
                del cur_cards[pair]
                del can_card[key]
                
        if cnt > 0:
            cnt -= 1
            continue

        for key in list(can_card.keys()):
            if coin <= 1: break
            pair = n+1-key
            if pair in can_card:
                coin -= 2
                cnt += 1
                del can_card[pair]
                del can_card[key]
                break
        
        if cnt > 0:
            cnt -= 1
            continue

        return answer
    return answer+1

 

 

---