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

문제

---

• n + 1 카드게임 (LV3)

n + 1 카드게임

1 ~ n 사이의 수가 적힌 카드와 동전 coin개가 있고 카드를 뽑는 순서가 리스트로 주어진다.
카드 뭉치에서 n/3장의 카드를 뽑아 먼저 가지게 되고 이후에는 각 라운드에서 두 장의 카드를 뽑게 된다.
뽑은 카드는 카드 한장 당 동전 하나를 소모하여 가질수도, 버릴 수도 있다.
다음 라운드로 진행하기 위해서는 카드에 적힌 수의 합이 n + 1이 되도록 카드 두 장을 내야 한다.
이러한 조건들이 주어질 때 최대 몇 라운드까지 도달할 수 있는지를 구하는 문제였다.

내 코드

---

여러가지 알고리즘을 떠올리며 풀어보려고 하였지만 잘 적용되지 않아서 단순 구현으로 풀어보았다.
1 ~ n 사이의 수 중에서 두 수의 합이 n + 1이 되려면 그 수의 파트너는 유일하다는 것이 힌트가 되었다.
접근한 방식은 visited 리스트를 만들어서 자신의 파트너 수 카드가 이전에 등장하였는지, 혹은 이미 보유 중인지를 확인 가능하도록 구현하였다.
그리고 can_use와 staging 변수에 그 결과를 업데이트하면서 진행해주었다.
모든 수의 파트너 수는 유일하므로 이후에 사용 완료 처리는 따로 해주지 않았다.

def solution(coin, cards):
    # -1: 등장 전, 0: 등장 후 & 구매 전, 1: 구매 후 & 사용 전
    n = len(cards)
    visited = [-1] * (n + 1)
    can_use = 0
    staging = 0
    ans = 1
    for i in range(n // 3):
        visited[cards[i]] = 1
        if visited[n + 1 - cards[i]] == 1:
            can_use += 1
    
    for i in range(n // 3, n, 2):
        for j in range(2):
            visited[cards[i + j]] = 0
            if coin > 0:
                if visited[n + 1 - cards[i + j]] == 1:
                    coin -= 1
                    can_use += 1
                elif visited[n + 1 - cards[i + j]] == 0:
                    staging += 1
        
        if can_use > 0:
            can_use -= 1
        elif coin > 1 and staging > 0:
            coin -= 2
            staging -= 1
        else:
            return ans
        ans += 1
    return ans

35일간 진행하였던 코테 알고리즘 스터디가 모두 마무리 되었다.
어떻게 보면 별거 아닐 수도 있지만 그래도 하루도 빼놓지 않고 모든 문제를 해결하였다는 사실에 조금은 뿌듯했다.