문제

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

---

입력

• 처음에 가진 동전수를 나타내는 정수 coin
• 카드를 뽑는 순서대로 카드에 적힌 수를 담은 1차원 정수 배열 cards

---

출력

게임에서 도달 가능한 최대 라운드의 수

---

풀이

제한조건

• 0 ≤ coin ≤ n
• 6 ≤ cards의 길이 = n < 1,000
  • cards[i]는 i+1번째로 뽑는 카드에 적힌 수를 나타냅니다.
  • 1 ≤ cards[i] ≤ n
  • cards의 원소는 중복되지 않습니다.
• n은 6의 배수입니다.

접근방법

단순 구현
경우의 수를 고려한 탐색으로 접근할 경우, 너무 많은 경우의 수가 발생한다.

따라서 최대한 단순화한 구현으로 생각해보자.

각 라운드별로 추가적으로 뽑은 숫자를 사용하기 위해서는 동전을 지불해서 카드를 얻어야 한다.
즉 최대한 기존의 카드를 이용해서 n+1을 만들어야 동전을 최소한으로 쓸 수 있다.

동전을 최소로 사용한다는 것은, 다음 라운드의 카드를 뽑아서 가질 수 있다는 의미이고, 이것은 다시 많은 라운드를 진행할 수 있는 바탕이다.

따라서 아래와 같은 흐름으로 접근한다.

1. 처음 시작하는 카드 뭉치에서 N+1을 만든다.
2. 1에서 불가능하다면, 추가적으로 뽑은 카드 중 1개를 사용하여 N+1을 만든다.
3. 2에서 불가능하다면, 추가적으로 뽑은 카드 2개를 이용하여 N+1을 만든다.
4. 3에서 불가능하다면, 다음 라운드로의 진행이 불가능하다.

-----------------------------------
1을 진행하기 위해서는 동전이 없어도 된다.
2를 진행하기 위해서는 동전이 최소 1개 있어야 한다.
3을 진행하기 위해서는 동전이 최소 2개 있어야 한다.

위의 조건대로 접근하면 된다.

---

코드

import java.util.*;

class Solution {
    Set<Integer> original, additional;
    public int solution(int coin, int[] cards) {
        int answer = 0;
        int len = cards.length;
        original = new HashSet();
        additional = new HashSet();
        
        int idx = len / 3;
        for(int i = 0 ; i < idx; ++i)
            original.add(cards[i]);
        
        int target = len + 1;   
        while(true){
            answer++;
            if(idx >= len){
                break;
            }
            additional.add(cards[idx]);
            additional.add(cards[idx+1]);
            idx += 2;
            boolean flag = false;
            // Step1. 최초 카드에서 해결할 수 있는지 확인.
            for(int i : original){
                if(original.contains(target - i)){
                    original.remove(i);
                    original.remove(target - i);
                    flag = true;
                    break;
                }
            }
            
            // Step2. 최초 카드에서 해결이 안되었다면
            if(!flag){
                // 최초 카드와 라운드 추가 카드 1장을 이용해서 해결 할 수 있는지 확인.
                if(coin > 0){ // 최소 1개 이상의 코인이 있어야 추가 카드를 받아서 사용할 수 있다.
                    for(int i : original){
                        if(additional.contains(target - i)){
                            original.remove(i);
                            additional.remove(target - i);
                            --coin;
                            flag = true;
                            break;
                        }
                    }
                }
            }
            
            // Step3. 그래도 해결이 안되었다면, 추가 카드들 간에 해결이 가능한 지 확인.
            if(!flag){
                if(coin > 1){ // 최소 2개 이상의 코인이 있어야 추가 카드를 중에서 해결이 가능하다.
                    for(int i : additional){
                        if(additional.contains(target - i)){
                            additional.remove(i);
                            additional.remove(target - i);
                            coin -= 2;
                            flag = true;
                            break;
                        }
                    }
                }
            }
            
            // 완성되지 않았다.
            if(!flag)
                break;
        }
        return answer;
    }
}