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

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/258707

프로그래머스

문제 설명

1, 2, ..., n이 적혀있는 카드가 하나씩 있는 덱과 동전을 이용해서 게임을 하려고 합니다.
카드뭉치는 위에서부터 차례대로 뽑으며, 게임의 룰은 다음과 같습니다.\

1. 처음에 coin개의 코인과 n/3 만큼의 카드를 손패로 가집니다. (n은 6의 배수입니다)

2. 게임은 1라운드부터 시작되며, 각 라운드가 시작될 때 덱 맨 위 카드 2장을 공개합니다. 만약 더 이상 뽑을 카드가 없다면 게임을 종료합니다.
공개된 카드는 각각 동전 1개를 소모해 가져갈 수 있습니다.

3. 카드에 적힌 수의 합이 n+1이 되도록 카드를 2장 내고 다음 라운드로 넘어갑니다. 만약 카드 두 장을 낼 수 없다면 게임을 종료합니다.

---

아이디어

● 종료조건 
게임의 종료조건은 "1. 뽑을 카드가 더이상 없다" "2. 더이상 카드를 낼 수 없다" 2가지 입니다.
"1. 뽑을 카드가 더이상 없다"는 덱에서 손패를 뽑은 후 남은 카드 수와 매 라운드 2장씩 카드를 뽑는 것을 통해 최대 n/3번 뽑을 수 있다는 것을 알 수 있습니다.

"2. 더 이상 카드를 낼 수 없다"는 들고있던 손패와 코인을 사용해 다음 카드 조합을 얻을 수 없을 때 종료됩니다.
여기서 매 라운드 얻을 수 있는 카드를 미리 결정하지 않고 나중에 선택해도 문제가 되지 않습니다.

● 코인 사용

1~n의 연속된 수로 n+1을 만드는 방법은 (1+n), (2+(n-1)) ... 와 같이 고유세트로만 만들 수 있습니다. 

기존에 손에 들고있던 카드들로만 n+1을 만들 수 있다면 0코인,
손에 들고 있는 카드와 덱에서 공개된 카드로 만들 수 있다면 1코인,
덱에서 공개된 카드 2장으로 만들 수 있다면 2코인을 소비한다고 생각할 수 있습니다.

그러면 손패와 덱에서 공개한 카드를 따로 기록하며, 만약 n+1을 만들 수 있는 신규 조합이 발견되면 몇 코인을 써서 만들 수 있는지 기록하고, 우선순위 큐에 넣어 매 라운드마다 1개씩 꺼내주는 방식이 가능할 것 같습니다.

---

코드

#include <vector>
#include <set>
#include <queue>
#include <algorithm>

using namespace std;

int n, targetNum, turn = 0, i, _coin;
//손패
set<int> ad; 
//덱에서 이미 공개한 카드들
set<int> grave; 
//낼 수 있는 카드조합. 0, 1, 2 : 각각 0 ~ 2코인 소모 else : 의미X
priority_queue<int> readyToUseCards; 
vector<int> cardNotUsed(1001, 1); 


bool UseCard()
{
    if(readyToUseCards.empty()) return false;
    auto useCard = readyToUseCards.top(); readyToUseCards.pop();
    
    if(_coin < -useCard)
        return false;

    _coin += useCard;
    return true;
}

int solution(int coin, vector<int> cards) {
    int n = cards.size();
    int targetNum = n + 1;
    _coin = coin;

    for(i = 0; i < n / 3; ++i)
    {
        ad.insert(cards[i]);
        if(cardNotUsed[cards[i]] && ad.find(targetNum - cards[i]) != ad.end())
        {
            cardNotUsed[cards[i]] = 0;
            cardNotUsed[targetNum - cards[i]] = 0;
            readyToUseCards.push(0);
        }
    }
    
    
    for(; i < n; i = i + 2)
    {
        turn++;
        int first = cards[i];
        int second = cards[i+1];
        if(cardNotUsed[first] && ad.find(targetNum - first) != ad.end())
        {
            readyToUseCards.push(-1);
            cardNotUsed[first] = 0;
            cardNotUsed[targetNum - first] = 0;
        }
        else
        {
            grave.insert(first);
            if(cardNotUsed[first] && grave.find(targetNum - first) != grave.end())
            {
                readyToUseCards.push(-2);
                cardNotUsed[first] = 0;
                cardNotUsed[targetNum - first] = 0;
            }
        }
        if(cardNotUsed[second] && ad.find(targetNum - second) != ad.end())
        {
            readyToUseCards.push(-1);
            cardNotUsed[second] = 0;
            cardNotUsed[targetNum - second] = 0;
        }
        else
        {
            grave.insert(second);
            if(cardNotUsed[second] && grave.find(targetNum - second) != grave.end())
            {
                readyToUseCards.push(-2);
                cardNotUsed[second] = 0;
                cardNotUsed[targetNum - second] = 0;
            }
        }

        if(!UseCard())
            break;
    }
    
    if(i == n) turn++;
    return turn;
}

성능요약 : 4.2MB, 0.06ms

---

꼭 오타를 애초에 안만들게 머리속에 생각이 끝나면 쓰기, 생각 정리 하기