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

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

  각 단계에서 최선의 선택을 하여 문제를 풀 수 있는 그리디 문제이다. 그리디 문제라고 생각은 하였으나 각 단계에서 최선의 선택이 무엇인지, 어떻게 구현할 수 있을지 생각하지 못해 풀 지 못한 문제였다.

 

[ 풀이 방법 ]

 처음에 가지고 있는 카드와 현재 라운드까지 뽑았던 카드를 각각 저장하고,

1. 동전을 사용하지 않고 다음 라운드로 진행할 수 있는 경우

  - 처음에 가지고 있는 n/3 장의 카드 중 2장을 사용하여 카드에 적힌 수의 합이 n+1이 되도록 만들 수 있는 경우

2. 동전을 1개만 사용하여 다음 라운드로 진행할 수 있는 경우

  - 처음에 가지고 있는 n/3 장의 카드 중 1장과 현재 라운드까지 뽑았던 카드 중 1장을 사용하여 카드에 적힌 수의 합이 n+1이 되도록 만들 수 있는 경우

3. 동전을 2개 사용하여 다음 라운드로 진행할 수 있는 경우

  - 현재 라운드까지 뽑았던 카드 중 2장을 사용하여 카드에 적힌 수의 합이 n+1이 되도록 만들 수 있는 경우

 

 map을 이용해 처음에 가지고 있는 카드와 현재 라운드까지 뽑았던 카드 각각 사용할 수 있는 카드의 개수를 저장하고,

더 이상 라운드를 진행할 수 없을 때까지 1 -> 2-> 3 순서대로 저장된 map을 탐색하며 최선의 선택을 하여 문제를 해결할 수 있다.

 

[ 회고 ]

 그리디 문제를 푸는 연습이 필요하다고 느꼈고, 비슷한 문제가 나왔을 때 풀 수 있도록 정리가 필요할 것 같다고 느꼈다.

 

 또한 map에 키를 인덱스로 접근 시, 해당 키에 값이 초기화되어 iterator로 순회 시 예상치 못한 결과가 발생했다. 따라서 iterator로 map을 순회하는 경우, map[idx]와 같이 접근하지 말고 map.count(idx)와 같은 방법으로 접근해야 할 것이다.

// Ex) check() 함수 구현 시
if(m2[target]) 
{
	// m2[target] = 0으로 초기화되어 iterator 순회 시 m2[target]도 탐색된다.
}

if(m1[it->first] && m2[target]) 
{
	// 따라서 m1과 m2 모두 1로 초기화 되었을 때(사용 가능한 카드가 존재할 때)만 해당 조건문이 실행되도록 변경해야만 정상적으로 기능이 수행된다.
}

if(m2.count(target)) {
	// 또는 count() 메서드를 이용해 m2의 target에 접근해도 초기화되지 않도록 해야한다.
}

 

 

[ 정답 코드 ]

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

using namespace std;

int n;

map<int, int> hands;
map<int, int> draws;

bool check(map<int, int>& m1, map<int, int>& m2) {
    
    for(auto it = m1.begin(); it != m1.end(); it++) {
        
        int target = n+1 - it->first;
        
        if(m2.count(target)) {
            
            m1.erase(it->first);
            m2.erase(target);
            
            return true;
        }
    }
    
    return false;
}

int solution(int coin, vector<int> cards) {
    int answer = 1;
    
    n = int(cards.size());
    int idx = n/3;
    
    for(int i = 0; i < idx; i++) {
        hands[cards[i]]++;
    }
    
    while(idx < n) {
        
        draws[cards[idx++]]++;
        draws[cards[idx++]]++;
        
        if(check(hands, hands)) {
            answer++;
        } else if(check(hands, draws) && coin >= 1) {
            answer++;
            coin--;
        } else if(check(draws, draws) && coin >= 2) {
            answer++;
            coin -= 2;
        } else {
            break;
        }
    }
    
    return answer;
}