문제

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

카카오 코테 때 못 풀었던 유일한 문제입니다..
다시 보니까 어려운 문제는 아니었는데 씁.

풀이

핵심은 카드 버리는 건 나중으로 미루는 것입니다.
처음 뽑은 카드를 공짜 카드, 나중에 뽑는 카드를 코인이 필요한 유료 카드라고 생각할 때,
매 턴 마다 비용이 최소인 카드 쌍을 선택해 버리면 됩니다.

초기화 부분:

 		n = cards.length; //
        
        boolean hand[] = new boolean[n+1];//손패에 카드가 있는지.
        boolean paid[] = new boolean[n+1];//공짜 카드인지.
        int coinLeft = coin; // 남은 코인
        
        //처음에 카드 뽑기.
        for(int i = 0; i < n/3; i++){
            hand[cards[i]] = true;
            paid[cards[i]] = true;
        }
        
        int answer = 1;

카드 뽑기

남은 코인이 있으면 카드를 뽑습니다. if를 없애도 딱히 상관은 없습니다.

		for(int i = n/3; i < n; i+=2){
            if(coinLeft > 0){
                hand[cards[i]] = true;
                hand[cards[i+1]] = true;
            }

버릴 카드 쌍 선택하기

1부터 n까지의 카드를 둘러 보면서

• 손패에 있는 카드 중 합이 n+1인 카드 쌍을 찾고,
• 남은 코인으로 비용 지불이 되는지 확인하고,
• 그렇게 찾은 카드 쌍 중 비용이 최소인 카드 쌍을 버립니다.

            boolean pass = false; //낼 수 있는 카드 쌍이 있는지
            int minCost = 3; // 최소 비용. 나올 수 있는 가장 큰 비용이 2므로 3으로 초기화
            int cardThrown = -1;// 버릴 카드.
            for(int j = 1; j <= n; j++){
                if(!hand[j]){ // 손패에 있는지
                    continue;
                }
                
                if(hand[n + 1 - j]){ //비용이 감당 되는지
                    int cost = (paid[j] ? 0 : 1) + (paid[n + 1 - j] ? 0 : 1);
                    if(coinLeft < cost || minCost <= cost){
                        continue;
                    }
                 
                    pass = true;
                    cardThrown = j;
                    minCost = cost;
                }
            }
            
            if(!pass){ // 버릴 카드가 없으면 끝.
                break;
            } 
            hand[cardThrown] = false; //
            hand[n + 1 - cardThrown] = false;
            coinLeft -= minCost;
                
            answer ++;
        }

n 최댓값이 1000이어서 조금 대충했지만 더 최적화를 하려면

• 하나의 카드와 합이 n+1이 되는 다른 카드는 단 하나 이므로 확인은 n/2까지만 하거나
• 손패를 따로 리스트로 관리

하는 방법이 있을 것 같습니다.

---

전체 코드

import java.util.*;

class Solution {
    static int n;
    
    public int solution(int coin, int[] cards) {
        n = cards.length;
        
        boolean hand[] = new boolean[n+1];
        boolean paid[] = new boolean[n+1];
        int coinLeft = coin;
        
        for(int i = 0; i < n/3; i++){
            hand[cards[i]] = true;
            paid[cards[i]] = true;
        }
        
        int answer = 1;
        for(int i = n/3; i < n; i+=2){
            if(coinLeft > 0){
                hand[cards[i]] = true;
                hand[cards[i+1]] = true;
            }
            
            boolean pass = false;
            int minCost = 3;
            int cardThrown = -1;
            for(int j = 1; j <= n; j++){
                if(!hand[j]){
                    continue;
                }
                
                if(hand[n + 1 - j]){
                    int cost = (paid[j] ? 0 : 1) + (paid[n + 1 - j] ? 0 : 1);
                    if(coinLeft < cost || minCost <= cost){
                        continue;
                    }
                 
                    pass = true;
                    cardThrown = j;
                    minCost = cost;
                }
            }
            
            if(!pass){
                break;
            } 
            hand[cardThrown] = false;
            hand[n + 1 - cardThrown] = false;
            coinLeft -= minCost;
                
            answer ++;
        }

        return answer;
    }
}