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

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

프로그래머스

 

해결 방법(실패)

생각을 조금 바꿔서, 매 턴 두장의 카드를 모두 손에 들 수 있고, 사용할때 코인을 지불하는 것으로 생각했다.

• hands에는 내가 현재 들고있는 카드가 들어있다.
• 매 웨이브마다, 2장의 카드를  손에 넣은 뒤, 가장 cost 가 적은 쌍을 손에서 버리고 "성공"을 리턴한다.
• 만약 성공하지 못했다면 해당웨이브에서 끝낸다.
• 만약 모든 카드더미를 다 소진했다면 그 다음웨이브에서 끝낸다.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


bool tryPop(const vector<int>& cards, vector<int>& hands, int& coin, int num){

    for(int i=0; i<hands.size(); i++){
        for(int j= i+1;j <hands.size();j++){
           
            if(hands[i]+hands[j] == num){
                int a= hands[i]; int b= hands[j];
                int use_coin = 0;
                auto it = find(cards.begin(), cards.end(),a);
                if(it!= cards.end() && it- cards.begin() >= cards.size()/3) use_coin ++;

                it = find(cards.begin(), cards.end(), b);
                if(it != cards.end() && it - cards.begin() >= cards.size()/3) use_coin ++;
                
                if(use_coin>coin) return false;
                coin -= use_coin;

                it = find(hands.begin(),hands.end(), a);
                hands.erase(it);
                
                it = find(hands.begin(), hands.end(), b);
                hands.erase(it);
                return true;
            }
        }
    }
    
    return false;
}

int solution(int coin, vector<int> cards) {

    vector<int> hands;
    for(int i=0; i<cards.size()/3; i++) hands.push_back(cards[i]);
    
    int wave =1;
    int default_card = cards.size()/3;
    int targetNum = cards.size()+1;
    int maxWave = (cards.size() - default_card )/2;
    while(wave <= maxWave){
        
        int idx = default_card + (wave-1)*2;
        hands.push_back(cards[idx]);
        hands.push_back(cards[idx+1]);
        
        bool success = tryPop(cards, hands, coin, targetNum);
        if(!success) return wave; //낼 두장이 없음.
        wave++;
    }
    
    return wave;
}

테스트케이스는 모두 성공했는데, 제출하기 하니까 7, 11, 12 번 문제에서 실패가 떳다. 엣지케이스가 있나보다. 원인을 모르겠다.

 

...

해결 방법(성공)

찾았따아아아아아아아아아아아아앙

위 방법이라면, 0코인으로 구매할 수 있는 상황에서 1코인을 사용하게 되는 경우가 발생한다.  12장 카드이고 손에 이렇게있을경우  [1,3,4,10,12]  10까지 무료이고 12부터 1코인을 내야하는 상황이다. 그런데 1과 12가 매치가 되어버리므로, {3,10}이 있음에도 불구하고 1원을 사용하게되는 것이다. 아이디어를 준 민수민수짱에게 감사를 표한다 호홋

 

그래서 코드에 최소 코인을 사용하는 세트 a 와 b를 찾아서 처리해주도록 tryPop()함수를 수정했다. 

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;


bool tryPop(const vector<int>& cards, vector<int>& hands, int& coin, int num){

    int a = 0; int b =0; int fcoin = 3;
    
    for(int i=0; i<hands.size(); i++){
        for(int j= i+1;j <hands.size();j++){
            if(hands[i]+hands[j] == num){
                
                int ca= hands[i]; int cb= hands[j]; int use_coin = 0;
                auto it = find(cards.begin(), cards.end(),ca);
                if(it!= cards.end() && it- cards.begin() >= cards.size()/3) use_coin ++;

                it = find(cards.begin(), cards.end(), cb);
                if(it != cards.end() && it - cards.begin() >= cards.size()/3) use_coin ++;
                
                if(use_coin <= fcoin) {
                    a = ca;
                    b = cb;
                    fcoin = use_coin;
                }
            }
        }
    }
    
    if(fcoin > coin || a==0 || b==0) return false;
    coin -= fcoin; //코인사용

    hands.erase(find(hands.begin(),hands.end(), a)); //손에서 제거
    hands.erase(find(hands.begin(),hands.end(), b));
    return true;
}

int solution(int coin, vector<int> cards) {

    vector<int> hands;
    for(int i=0; i<cards.size()/3; i++){
      hands.push_back(cards[i]);  
    } 
    
    int wave =1;
    int default_card = cards.size()/3; //기본 보유중인 카드의 수 
    int targetNum = cards.size()+1; //합해서 tagetNum이 되는 숫자
    int maxWave = (cards.size() - default_card )/2; //진행가능한 최대 wave
    while(wave <= maxWave){
        
        int idx = default_card + (wave-1)*2;
        hands.push_back(cards[idx]);
        hands.push_back(cards[idx+1]);
        
        bool success = tryPop(cards, hands, coin, targetNum);
        if(!success) return wave; //낼 두장이 없음.
        wave++;
    }
    
    return wave;
}