[2024KAKAO WINTER INTERNSHIP] N+1 카드게임

코딩테스트 연습 - n + 1 카드게임 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

2024KAKAO WINTER INTENSHIP N+1 카드게임 문제입니다

 

 

해당 문제는 매 라운드 마다 손에있는카드 2장의 합이 N+1이 되도록 버려 다음라운드로 진행고,

매라운드의 시작시 카드 2장을 뽑아 원하는 카드를  주어진 코인을 통해 보충해 나가며, 도달가능한 최대 라운드를 구하는 문제입니다.

게임 방식

1. 처음 카드 뭉치에서 n/3장을 뽑아 가집니다(n은 6의 배수) 교환 가능한 동전 Coin개를 가지고있습니다.

2. 각 라운드 시작시 2장의 카드를 뽑습니다 이때 카드 뭉치에 남은 카드가 없다면 게임을 종료합니다

뽑은 카드는 카드 한 장당 동전 하나를 소모해 가지거나, 소모하지않고 버릴 수 있습니다.

3. 카드에 적힌 수의 합이 n+1이 되도록 카드 두장을 내고 다음 라운드로 진행합니다 낼수 없다면 게임을 종료합니다

 

 

문제의 이해

입력 : 3 6 7 2 1 10 5 9 8 12 11 4

 

처음 시작카드 3 6 7 2 를 들고 시작합니다

1 10 두장을 코인2개를 사용하여가지고 1 10 을 내며 다음라운드로 진행합니다

5 9 가 나왔지만 둘다 코인을 사용하지않고 6 7 을 내며 다음라운드로 진행합니다

8 12 중에 12만 코인을 사용하고 1 12 을 내며 다음라운드로 진행합니다

11 4 중에 11에 마지막 코인을 사용하며 2 11을 내며 다음라운드로 진행합니다

뽑을 카드가 없기때문에 게임을 종료합니다

이런 방법으로 5라운드에 도달할 수 있습니다

 

 

문제의 접근

우리는 다음 나올 카드의 순서를 이미 알고있습니다 이것은 정답을 이미 알고있다는것을 의미합니다

이점은 우리에게 매우 유리하게 작용합니다

2장의 카드는 반드시 Pair을 이루도록 문제는설계되어있습니다

N+1에 해당하는 Pair을 우리는 매라운드가 진행할때마다 찾아주며 카드를 버린다는 문구에 현혹되지않고

뽑히는 카드들을  Pair을 이루어주도록 할 것입니다

이때 3가지 경우가 발생합니다

각 경우 마다 소비되는 Coin의 갯수가 달라집니다

1. 처음 받은 시작카드에서 Pair가 발생하는 경우         Coin -0

2. 뽑은 카드와 시작 카드에서  Pair가 발생하는 경우   Coin -1

3. 새로 뽑은 카드끼리 Pair가 발생하는 경우                Coin -2

뽑은 카드를 손패로 넣는 과정에서 소비되는 코인의 개수가 달라지기 때문에 이런 차이가발생합니다

위의 순위에 우선순위를 두어 손패를 털어주며 라운드를 진행할것입니다

라운드가 진행될때 해당 케이스를 코인이 하나 소비되는 OneCoincase와 코인이 두개 소비되는TwoCoinCase 두가지로 나누어 Pair가 발생할 때마다 해당케이스를 증가시켜주고 라운드가 진행될때 OneCoinCase를 우선순위로 소모해주며 진행 할것입니다

 

 

해당 문제를 풀기위해

1. 시작 손패를 정리합니다

2. 카드의 Pair를 마추며 OnecoinCase와 TwoCoinCase의 증가를 합니다

3. OneCoinCase를 우선순위로 감소시켜주며 재귀를 진행합니다

4. 예외처리를 해주고 라운드를 리턴해줍니다

 

 

1. 시작 손패를 정리합니다

카드의 Pair데이터를 저장할 StartCards와 OtherCards를 만들어주고

n/3 에 해당하는 카드 지점까지 StartCards에 넣어줍니다

이때 Pair가 발생한다면 Onecoincase와 Coin을 같이 증가시켜줍니다

완성된 Pair는 지워주며 데이터를 관리합니다

2. 카드의 Pair를 마추며 OnecoinCase와 TwoCoinCase의 증가를 합니다

2장의 카드를 StartCards와 OtherCards 두가지 map에 순차적으로 Pair를 만들어줍니다

이때 StardCards에서 페어가만들어진다면 OncoinCase를 증가시켜주고

OtherCards에서 페어가 만들어진다면 TwoCoinCase를 증가시켜줍니다

3. OneCoinCase를 우선순위로 감소시켜주며 재귀를 진행합니다

남은 코인의 개수와 각각의 케이스의 남은 개수를 확인하여

코인을 적게 소비하는 OneCoinCase를 우선순위로 감소시켜주며 재귀를 진행합니다

4. 예외처리를 해주고 라운드를 리턴해줍니다

나올 수 있는 최대 라운드를 넘어가는 오류(너무 잘풀린경우)를 예외처리 해주며 재귀를 마무리합니다

 

 

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

map<int, int> StartCards;
map<int, int> OtherCards;
int game(vector<int> Cards, int stage, int chance, int lostcoin, int NPlusone);
int solution(int coin, vector<int> cards) {

    int cardsSize = cards.size();

    int thirdPoint = cardsSize / 3;
    int onecoincase = 0;

    for (int i = 0; i < thirdPoint; i++)
    {
        if (StartCards.find((cardsSize - cards[i] + 1)) == StartCards.end())
        {
            StartCards.insert(std::make_pair(cards[i], 0));
        }
        else
        {
            StartCards.erase(cardsSize - cards[i] + 1);
            onecoincase++;
            coin++;
        }
    }
    vector<int> Deck(cards.begin() + thirdPoint, cards.end());

    return game(Deck, onecoincase, 0, coin, cardsSize);
}

int game(vector<int> Cards, int onecoincase, int twocoincase, int remainingcoins, int NPlusone)
{
    if (Cards.size() == 0)
    {
        return 1;
    }

    for (int i = 0; i < 2; i++)
    {

        if (StartCards.find((NPlusone - Cards[i] + 1)) != StartCards.end())
        {
            if (remainingcoins >= 1)
            {
                onecoincase++;
                StartCards.erase((NPlusone - Cards[i] + 1));
            }
        }
    }

    for (int i = 0; i < 2; i++)
    {

        if (OtherCards.find((NPlusone - Cards[i] + 1)) == OtherCards.end())
        {
            OtherCards.insert(std::make_pair(Cards[i], 0));
        }
        else
        {
            OtherCards.erase((NPlusone - Cards[i] + 1));
            twocoincase++;
        }
    }

    Cards.erase(Cards.begin(), Cards.begin() + 2);

    if (onecoincase >= 1 && remainingcoins >= 1)
    {
        return 1 + game(Cards, onecoincase - 1, twocoincase, remainingcoins - 1, NPlusone);
    }
    else if (twocoincase >= 1 && remainingcoins >= 2)
    {
        return 1 + game(Cards, onecoincase, twocoincase - 1, remainingcoins - 2, NPlusone);
    }
    else
    {
        return 1;
    }

}

 

 

후기

 

처음에는 재귀 기반의 완전탐색이 눈에 보였습니다 하지만 너무 비효율적인거같아 다시풀었던거같습니다.

문제의 키포인트는 우리는 카드가 뭐가 나올지 다 알고있다는점인거같습니다.

때문에 나오는 카드들을 버린다는 문구에 현혹되지않고 푼다면 어렵지않게 풀 수 있을거같습니다