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

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

프로그래머스

 

 

 

카드 게임을 진행할 수 있는 최대 라운드 수를 구해야 함

 

초기 접근 방식

매 라운드마다 다음과 같은 경우의 수가 존재하므로, dfs 알고리즘을 떠올림

: 카드 두 장 구매 / 카드 한 장 구매 / 구매하지 않음

 

하지만 dfs를 적용할 경우 카드 배열의 최대 길이는 1000이니까

대략 3^500 의 시간복잡도가 발생 > 시간초과

 

따라서 greedy 방식으로 바꾸어서 풀이(타 풀이를 참고했다..)

 

- 매 라운드마다 카드를 버리는 게 아닌, 따로 저장해 두기

- 코인 소모를 최소한으로(너무당연함)

 

 

문제에서의 입출력 예#3을 보면, 2라운드에서 12, 11 두 장의 카드를 가지면서, 해당 라운드에서는 카드 12 만(기존 카드 1과 함께) 소모. 3라운드에서 나머지 11 카드를 소모하여 플레이한다.

-> 이 때 11이라는 카드를 2라운드에서 갖고오든 3라운드에서 갖고오든 동일하게 취급되기 때문에, 해당 라운드를 플레이할 페어가 존재하다면 최대한 코인을 소모하지 않으면서 게임을 이어나가야 최적의 결과를 얻을 수 있다 - 그래서 greedy

 

 

import java.util.*;
class Solution {
    public int solution(int coin, int[] cards) {
        //init
        int currPair = 0, currCoin = coin;
        int goal = cards.length + 1;
        HashSet<Integer> currCards = new HashSet<>();
        HashSet<Integer> remain = new HashSet<>();
        for(int i=0; i<cards.length/3; i++){
            int curr = cards[i];
            if(!currCards.contains(goal - curr)){
                currCards.add(cards[i]);
            }else {
                currCards.remove(goal - curr);
                currPair ++;
            }
        }

        int round = 0;
        for(int i=cards.length/3; round <= currPair && currCoin > 0 && i<cards.length; i+=2){
            for(int j=0; j<2; j++){
                if(currCoin >=1 && currCards.contains(goal - cards[i+j])) { //new - old matching
                    currCoin--;
                    currPair++;
                    currCards.remove(goal - cards[i + j]);
                }else{
                    remain.add(cards[i+j]);
                }
            }

            if(round >= currPair && currCoin >= 2){ //new - new matching
                for(int card : remain){
                    if(remain.contains(goal - card)){
                        remain.remove(card);
                        remain.remove(goal-card);
                        currPair++;
                        currCoin-=2;
                        break;
                    }
                }
            }
            round ++;
        }
        return currPair + 1;
    }
}