[프로그래머스] n + 1 카드게임 (c++) 그리디 + 구현, 벡터의 삭제

출처 : https://school.programmers.co.kr/learn/courses/30/lessons/258707?language=cpp

프로그래머스

풀이 방법

제일 처음에는 완전 탐색을 이용해가 위해 dfs를 활용해서, 모두 선택하는 경우, 하나만 선택하는 경우, 둘 다 선택하는 경우를 백트레킹을 활용해서 풀이하였다.

하지만 시간 초과가 발생했다.

 

이에 그리디를 활용해서 풀이할 수 있음을 알게 되었다.

 

문제의 핵심은 코인을 사용해 짝을 맞출 수 있는 카드를 별도로 저장해 두는 것이다. 이를 통해, 기존에 가진 카드만으로는 짝을 맞추지 못할 경우 코인을 사용해 얻을 수 있는 카드 중에서 짝이 있는 경우를 찾아 짝을 맞추는 방식이다.

 

또 다른 핵심은 모든 카드의 짝이 정해져 있다는 것이다.
둘의 합이 n+1이어야 하기 때문에 i카드라면 n+1-i카드가 존재해야 한다.

 

그러므로 매 라운드마다 카드 2개를 코인을 사용해서 얻을 수 있는 리스트로 저장하고, 코인을 0개, 1개, 2개 사용하는 순서로 진행하면 된다.

 

이때 빠른 탐색을 위해 unorderd_map을 사용해서, 카드 숫자에 해당하는 카드의 리스트에서 인덱스를 빠르게 구할 수 있었다.

벡터에서 특정 원소를 제거하는 방법

hands.erase(remove(hands.begin(), hands.end(), pair[0]), hands.end());

#include <vector>
#include <deque>
#include <unordered_map>
#include <algorithm>

using namespace std;

int solution(int coin, vector<int> cards) {
    int answer = 1;

    // 초기화
    vector<int> hands(cards.begin(), cards.begin() + cards.size() / 3); //지금 들고 있는 것
    deque<int> remain_cards(cards.begin() + cards.size() / 3, cards.end()); // 남은 카드
    vector<int> able_remain_cards; // 남은 카드 중에 가능한 카드
    int cur_round = 0;

    unordered_map<int, bool> hands_dict; // 손에 있는 카드가 존재하는지 확인하기 위한 딕셔너리
    for (int v : hands) { // 현재 들고 있는 카드 true로 초기화
        hands_dict[v] = true;
    }

    while (true) {
        cur_round++;
        if (hands.empty() && remain_cards.empty()) {
            break;
        }

        // 남은 카드에서 2장을 가져옴
        if (!remain_cards.empty()) {
            able_remain_cards.push_back(remain_cards.front());
            remain_cards.pop_front();
        }
        if (!remain_cards.empty()) {
            able_remain_cards.push_back(remain_cards.front());
            remain_cards.pop_front();
        }

        vector<int> pair;
        for (int c : hands) {
            if (hands_dict.find((cards.size() + 1) - c) != hands_dict.end()) { // 손에 있는 카드와 짝이 맞는 카드가 있는 경우
                pair.push_back(c);
                pair.push_back((cards.size() + 1) - c);
                break;
            }
        }

        if (!pair.empty()) { //손에 있는 카드에서 짝을 찾아진 카드를 제거한다.
            hands.erase(remove(hands.begin(), hands.end(), pair[0]), hands.end());
            hands.erase(remove(hands.begin(), hands.end(), pair[1]), hands.end());

            hands_dict.erase(pair[0]); // 딕셔러니 제거
            hands_dict.erase(pair[1]);
            continue; // 다음 라운드로 진행
        }

        if (coin == 0) { 
            break;
        }
        // 코인 1개를 사용해야 합니다.
        for (int able_card : able_remain_cards) { // 코인을 사용해서 짝을 찾을 수 있는 카드 중에 가능한 경우 코인 하나 사용
            if (hands_dict.find((cards.size() + 1) - able_card) != hands_dict.end()) {
                pair.push_back((cards.size() + 1) - able_card);
                pair.push_back(able_card);
                break;
            }
        }

        if (!pair.empty()) {
            hands.erase(remove(hands.begin(), hands.end(), pair[0]), hands.end());
            able_remain_cards.erase(remove(able_remain_cards.begin(), able_remain_cards.end(), pair[1]), able_remain_cards.end());
            coin--;

            hands_dict.erase(pair[0]);
            continue;
        }

        if (coin == 1) {
            break;
        }
        //코인 2개를 사용하는 경우
        unordered_map<int, bool> able_remain_card_dict;
        for (int v : able_remain_cards) {
            able_remain_card_dict[v] = true;
        }

        for (int c : able_remain_cards) {
            if (able_remain_card_dict.find((cards.size() + 1) - c) != able_remain_card_dict.end()) {
                pair.push_back(c);
                pair.push_back((cards.size() + 1) - c);
                break;
            }
        }

        if (!pair.empty()) {
            able_remain_cards.erase(remove(able_remain_cards.begin(), able_remain_cards.end(), pair[0]), able_remain_cards.end());
            able_remain_cards.erase(remove(able_remain_cards.begin(), able_remain_cards.end(), pair[1]), able_remain_cards.end());
            coin -= 2;
            continue;
        }

        break;
    }

    return cur_round;
}