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

프로그래머스 n+1카드게임 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

1~n사이의 수가 적힌 카드가 하나씩 있는 카드뭉치와 동전 coin개를 사용하여 게임을 하려고 한다.
처음에 카드 뭉치에서 카드 n/3장을 뽑아 모두 가지며(n은 6의 배수) 카드와 교환 가능한 동전 coin개를 가지고 있습니다.
게임은 1라운드부터 시작되며, 각 라운드가 시작할 때 카드를 두 장 뽑습니다. 카드 뭉치에 남은 카드가 없다면 게임을 종료합니다. 뽑은 카드는 카드 한 장당 동전 하나를 소모해 가지거나, 동전을 소모하지 않고 버릴 수 있습니다.
카드에 적힌 수의 합이 n+1이 되도록 카드 두 장을 내고 다음 라운드로 진행할 수 있으며 만약 카드 두 장을 낼 수 없다면 게임을 종료합니다.
게임에서 도달할 수 있는 최대 라운드를 구해야합니다.

문제 풀이

처음에 플레이어가 가질 수 있는 카드와 다음으로 라운드마다 뽑을 수 있는 카드들을 coin수 만큼 뽑으며 도달 가능한 최대 라운드 수를 알아내야 합니다.
라운드마다 2장을 뽑고 원하는만큼 coin을 사용하여 카드를 가지고 나머지는 버리는 것과 다르게, 최대 라운드 수를 구할 때는 카드를 미리 뽑아두고 나중에 사용하는 경우도 생길 수 있기 때문에 뽑은 카드들을 따로 저장해둔 뒤 필요할 때 coin을 이용해 카드를 사용하는 방법도 가능합니다.
즉, 최대 라운드를 알기 위해서는 최소한의 coin을 사용하여 라운드를 진행해야 되기 때문에 coin을 사용하지 않고 n+1값을 만들 수 있는가, coin을 1개 사용하여 n+1값을 만들 수 있는가, coin을 2개 사용하여 n+1값을 만들 수 있는가를 순서대로 확인하며 라운드를 진행하면 됩니다. 모든 경우가 불가능하면 라운드를 이어나갈 수 없다 판단하면 됩니다.

한 카드로 n+1값을 만들 수 있는지 확인하는 방법은 여러 가지 존재하며, 저는 플레이어가 처음에 들고 있는 카드들과 뽑았던 카드들을 다른 값으로 전부 저장해주며 배열을 통해 특정한 번호를 가진 카드가 존재하는지 저장해두었습니다.

만약 예제로 {1, 2, 3, 4, 5, 6}가 주어진다면(n은 주어진 카드의 수)
처음에 플레이어가 가지는 카드는 1, 2이며, arr[1] = 1, arr[2] = 1 이런식으로 배열에 값을 넣어두어 map처럼 찾는 카드 번호 인덱스에 값을 저장해두어 빠른 접근이 가능하도록 하였습니다.
이후에 뽑은 카드들은 배열에 2로 저장하여 이 카드는 뽑은 카드라는 것을 알려주었습니다.

이렇게 카드를 저장해둔 배열을 참고하며 라운드를 이어나갈 수 없을 때까지 진행시켜주면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int n;
int coinCount;
queue<int> player;
vector<int> checkNum;
queue<int> nextCard;
pair<int, int> p;

bool checkCard(int checkNumber)
{
    
    int qSize = player.size();
    for(int i = 0; i < qSize; i++)  //현재 카드로 n+1수를 만들 수 있는지 확인
    {
        int num = player.front();   player.pop();
        if(checkNum[num] == 0)  //이미 사용한 카드거나 없다면
            continue;
        
        if(checkNum[(n+1)-num] != 0){   //카드 중에 n+1을 만들 수 있는 카드가 있다면
            if(checkNumber == 0)    //코인 0개를 사용하는 경우
            {
                if(checkNum[(n+1)-num] != 1 || checkNum[num] != 1)  //두 카드가 플레이어가 들고 있는 카드일 경우
                {
                    player.push(num);
                    continue;
                }

                p = make_pair(checkNum[num], checkNum[(n+1)-num]);
                checkNum[num] = 0;
                checkNum[(n+1)-num] = 0;
                return true;
            }else if(checkNumber == 1)    //코인 1개를 사용하는 경우
            {
                if(checkNum[(n+1)-num] == 1 && checkNum[num] == 2 && coinCount >= 1 ||
                   checkNum[(n+1)-num] == 2 && checkNum[num] == 1 && coinCount >= 1)    //두 카드 중 한개만 뽑을 카드일 경우
                {
                    coinCount -= 1;
                    p = make_pair(checkNum[num], checkNum[(n+1)-num]);
                    checkNum[num] = 0;
                    checkNum[(n+1)-num] = 0;
                    return true;
                }
            }else if(checkNumber == 2)    //코인 2개를 사용하는 경우
            {
                if(checkNum[(n+1)-num] == 2 && checkNum[num] == 2 && coinCount >= 2)    //두 카드 모두 뽑을 카드일 경우
                {
                    coinCount -= 2;
                    p = make_pair(checkNum[num], checkNum[(n+1)-num]);
                    checkNum[num] = 0;
                    checkNum[(n+1)-num] = 0;
                    return true;
                }
               
            }
        }
        player.push(num);
    }
    
    return false;
}

int solution(int coin, vector<int> cards) {
    int answer = 0;
    n = cards.size();
    checkNum.assign(1001, 0);
    int index = n/3;
    coinCount = coin;
    
    //처음에 들고 갈 카드 저장
    for(int i = 0; i < n/3; i++)
    {
        player.push(cards[i]);
        checkNum[cards[i]] = 1;
    }
    
    while(true) //3가지의 경우가 불가능할때까지 반복
    {
        answer++;
        if(index >= cards.size()-1) //뽑을 카드가 없다면 끝
            break;
        
        bool isComplete = false;
        checkNum[cards[index]] = 2;
        checkNum[cards[index+1]] = 2;
        player.push(cards[index]);
        player.push(cards[index+1]);
        index += 2;
        
        isComplete = checkCard(0);
        if(isComplete) //현재 있는 카드로 체크
            continue;
        
        if(coinCount > 0)
        {
            isComplete = checkCard(1);  //코인 한 개를 사용하여 n+1을 만들 수 있는지 확인
            if(isComplete)
                continue;
            
            isComplete = checkCard(2);  //코인 두 개를 사용하여 n+1을 만들 수 있는지 확인
            if(isComplete)
                continue;
        }
        if(!isComplete)
            break;
    }
    
    return answer;
}

출저

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