[Programmers] n + 1 카드게임

문제 링크

프로그래머스 n+1 카드게임

문제

• 1~n 사이의 수가 각각 하나씩 적힌 카드뭉치와 coin을 가지고 게임을 시작한다.
• n/3 장을 처음에 모두 뽑아 가진다.
• 각 라운드에서 카드 두장을 뽑는다. 뽑은 카드는 코인을 소모해서 가질지 소모하지 않고 버릴지 선택할 수 있다.
• 매 라운드마다 합이 n+1이 되는 카드 두 장을 내야 다음 라운드로 넘어갈 수 있다.

풀이

제출할 수 있는 카드 쌍의 개수를 availSet변수에 저장하여 매 라운드마다 availSet>0인지 확인해주었다.

availSet을 얻을 수 있는 경우는 3가지이다.
1. 처음 가지고 시작하는 n/3장의 카드만으로 조합
2. 처음 가지고 시작한 n/3 중 한 장 + 라운드에서 뽑은 1장(코인 1개 소모)
3. 라운드에서 뽑은 카드 2장(코인 2개 소모)

최대 라운드에 도달하기 위해서는 코인을 최대한 적게 사용하는 것이 핵심이다. 따라서 매 라운드마다 코인을 가장 적게 소모하여 availSet을 확보해야하므로 그리디 알고리즘임을 알 수 있었다.

위의 3가지 경우에서 1번의 경우는 처음 시작 전에 모두 확인 후 availSet을 업데이트 해주므로 이후 반복문에서는 확인할 필요가 없다.

라운드를 진행하면서 코인 1개로 availSet을 만들 수 있다면 만들어두는 것이 최선이다. 따라서 뽑은 카드와 가지고 있는 카드가 합이 n+1이 되는 경우에는 무조건적으로 코인을 소모해 카드를 가져온다.

코인 2개를 사용해 availSet을 만드는 경우는 만약 코인을 사용하지 않을 경우 라운드를 진행할 수 없을 때만 코인을 소모해 카드 2장을 가져온다.

코인을 2개 소모하는 경우를 확인할 때, 한 쌍이 확인된 경우 해당 시점에서 탐색을 중지하고 다음 라운드로 넘어가야하는데, 확인 후에도 계속 코인 2개가 가능한 쌍을 탐색하도록 코드를 짜서 한참을 맞왜틀 했다.

코드

class Solution {
    public int solution(int coin, int[] cards) {
        int answer = 1;
        int n = cards.length;
        int availSet = 0;
        boolean[] myCard = new boolean[n+1];
        boolean[] passCard = new boolean[n+1];
        
        for(int i=0; i<n/3; i++){
            myCard[cards[i]] = true;
            if(myCard[n+1-cards[i]]) availSet++;
        }
        
        int firstCard, secondCard;
        for(int i=n/3; i<n; i+=2){
            firstCard = cards[i]; secondCard = cards[i+1];
            
            //짝 카드를 가지고 있는 경우와 아닌 경우
            if(myCard[n+1-firstCard] && coin>0){
                coin--; availSet++;
            }
            else passCard[firstCard] = true;
            
            if(myCard[n+1-secondCard] && coin>0){
                coin--; availSet++; 
            }
            else passCard[secondCard] = true;
            
            //가능한 셋이 있으면 일단 넘어간다.
            if(availSet>0) availSet--;
            else if(coin>=2){
                for(int j=1; j<=n; j++){
                    if(passCard[j] && passCard[n+1-j]){
                        passCard[j] = false; passCard[n+1-j] = false;
                        coin-=2;
                        availSet++;
                        break;
                    }
                }
                if(availSet>0) availSet--;
                else return answer;
            }
            else return answer; 
            answer++;
        }
        
        return answer;
    }
}