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

이 문제는 그리디 알고리즘으로 풀었다.

 

이 문제에서 핵심은 카드를 버리지 않는 것이다. 즉, 버리는 대신 어딘가 저장해둔 뒤에 필요할 때 코인을 주고 쓰는 것이다.

이걸 인지하면 문제가 매우 쉬워지고, 단순 구현 문제로 바뀌게 된다.

 

그리디 알고리즘이 적용되는 부분은 N + 1을 만들 때 적용되는데, 우선순위를 다음과 같이 해서 문제를 풀었다.

1. 내가 가진 카드만으로 n + 1 만들 수 있을 때

2. 버린 덱에서 한 장 + 내가 가진 카드 한 장으로 만들 수 있을 때

3. 버린 덱에서 두 장 모두 가져와야 할 때

 

매 라운드마다 카드를 두 장 뽑을 수 있는데, 바로 discard set에 넣어서 구현을 단순화했다.

 

주의할 점은 루프가 다 돌아서 끝나는 경우에는 answer + 1을 해줘야 한다는 점이다.

#include <string>
#include <vector>
#include <set>
#include <queue>

using namespace std;

int sumNumber;
vector<int> my;
set<int> discard;

void init(vector<int>& cards) {
    int size = cards.size();
    
    for (int i = 0; i < size / 3; i++) {
        int num = cards[i];
        my.push_back(num);
    }
}

bool checkNoCoin() {
    int mySize = my.size();
    
    for (int i = 0; i < mySize; i++) {
        for (int j = i + 1; j < mySize; j++) {
            if (my[i] + my[j] == sumNumber) {
                my.erase(my.begin() + j);
                my.erase(my.begin() + i);
                
                return true;
            }
        }
    }
    
    return false;
}

bool checkOneCoin() {
    int mySize = my.size();
    
    for (int i = 0; i < mySize; i++) {
        int num = my[i];
        
        int restNum = sumNumber - num;
        
        if (discard.find(restNum) != discard.end()) {
            my.erase(my.begin() + i);
            discard.erase(restNum);
            return true;
        }
    }
    return false;
}

bool checkTwoCoin() {
    vector<int> temp;
    
    for (auto iter = discard.begin(); iter != discard.end(); iter++) {
        temp.push_back(*iter);
    }
    
    int size = temp.size();
    
    for (int i = 0; i < size; i++) {
        for (int j = i + 1; j < size; j++) {
            if (temp[i] + temp[j] == sumNumber) {
                discard.erase(temp[i]);
                discard.erase(temp[j]);
                return true;
            }
        }
    }
    return false;
}

int solution(int coin, vector<int> cards) {
    int answer = 0;
    
    sumNumber = cards.size() + 1;
    init(cards);
    
    int size = cards.size();
    
    int i;
    for (i = size / 3; i < size; i += 2) {
        answer++;
        int firstCard = cards[i];
        int secondCard = cards[i + 1];
        
        discard.insert(firstCard);
        discard.insert(secondCard);
        
        if (checkNoCoin()) {
            continue;
        }
        
        if (coin >= 1 && checkOneCoin()) {
            coin--;
            continue;
        }
        
        if (coin >= 2 && checkTwoCoin()) {
            coin -= 2;
            continue;
        }
        
        break;
    }
    
    if (i == size) {
        answer++;
    }
    
    return answer;
}