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

문제

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

프로그래머스

풀이

SETTING

n/3의 코드는 hand에 가져오고 나머지는 deck에 둔다

 

MAIN

우선 매번 deck에서 카드 두장을 pending으로 가져온다

코인을 덜 쓸수록 유리하므로

코인을 덜 써도 check()이 true를 반환할 경우 그렇게 한다.

(손에 있는 카드 최대로 활용)

 

Check함수

deck1과 deck2의 카드들 중에서

둘을 합쳐 n+1를 만들 수 있는 카드가 있다면

그 두 카드를 쓰는 것이 가장 효율적이다

해당 카드들을 찾아 deck에서 삭제한 후

가능 여부를 반환한다.

 

코드

#include <deque>
#include <unordered_set>
#include <vector>
#include <algorithm>

using namespace std;
int target;

//deck1,deck2에서 target을 만들 수 있는 숫자를 찾아 제거
bool check(vector<int>& deck1, vector<int>& deck2) 
{
    unordered_set<int> operand(deck2.begin(), deck2.end());
    for (auto it = deck1.begin(); it != deck1.end(); ++it) 
    {
        if (operand.find(target - *it) != operand.end()) 
        {
            // Remove the card from deck1
            int card = *it;
            deck1.erase(it);
            
            // Remove the card from deck2
            auto it2 = find(deck2.begin(), deck2.end(), target - card);
            if (it2 != deck2.end()) { deck2.erase(it2); }
            
            return true;
        }
    }
    return false;
}

int solution(int coin, vector<int> cards) 
{
    //SETTING
    target=cards.size()+1;
    
    vector<int> hand(cards.begin(), cards.begin() + cards.size() / 3);
    deque<int> deck(cards.begin() + cards.size() / 3, cards.end());
    vector<int> pending;
    
    int turn = 1;
    
    //MAIN
    while (coin >= 0 && !deck.empty()) 
    {
        //get two cards from deck
        pending.push_back(deck.front());
        deck.pop_front();
        if (!deck.empty()) 
        {
            pending.push_back(deck.front());
            deck.pop_front();
        }
        
        //check
        if (check(hand, hand)) {  } 
        else if (coin >= 1 && check(hand, pending)) { coin -= 1; }
        else if (coin >= 2 && check(pending, pending)) { coin -= 2; } 
        else { break; }
        
        turn += 1;
    }
    //RESULT
    return turn;
}

 

참고 사이트

안풀려서 이분꺼 참고해서 풀었다..!

https://tolerblanc.github.io/programmers/programmers-nplueone-cardgame/

[프로그래머스] (Lv.3) n + 1 카드게임