[2024 KAKAO WINTER INTERNSHIP] n + 1 카드게임

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

프로그래머스

 

가장 중요한 포인트는 이번 라운드에서 새로 뽑는 2개의 카드가 앞으로 필요할지, 필요 없을지 미리 알 수 없다. 따라서 2개의 카드 중 몇 개의 카드를 동전을 주고 가져와야 하는지 알 수 없다. 이 부분이 가장 고민이었다. 그런데!! 다음과 같이 풀면 된다.

• 새로 뽑는 2개의 카드를 별도의 set에 담아두자.
• 그리고 나중에 필요할 때 set에서 필요한 카드를 가져오고 그만큼 coin을 감소시키면 된다!!!!!!!

import java.util.*;

class Solution {
    
    int coin;
    int[] cards;
    int n;
    Set<Integer> myCardSet = new HashSet<>();
    Set<Integer> additionalCardSet = new HashSet<>();
    
    public int solution(int coin, int[] cards) {
        this.coin = coin;
        this.cards = cards;
        n = cards.length;
        for (int i = 0; i < n / 3; i++) {
            myCardSet.add(cards[i]);
        }
        
        int answer = 0;
        int idx = n / 3;
        
        while (true) {
            answer++;
            
            // 뽑을 카드가 없는 경우 -> 끝내기
            if (idx >= n) {
                break;
            }
            
            // 1. 2개의 새로운 카드를 뽑아서 별도의 set에 담아두기
            additionalCardSet.add(cards[idx++]);
            additionalCardSet.add(cards[idx++]);
            
            // 2. 이미 가진 카드에서 낼 수 있으면 내기
            boolean flag = false;
            for (int card : myCardSet) {
                if (myCardSet.contains(n + 1 - card)) {
                    myCardSet.remove((Object) card);
                    myCardSet.remove((Object) (n + 1 - card));
                    flag = true;
                    break;
                }
            }
            
            // 3. 그렇지 않으면 additional과 섞어서 내기 (coin 감소)
            if (!flag && coin >= 1) {
                // 3-1. myCardSet에서 1개, additionalCardSet에서 1개
                for (int card : myCardSet) {
                    if (additionalCardSet.contains(n + 1 - card)) {
                        myCardSet.remove((Object) card);
                        additionalCardSet.remove((Object) (n + 1 - card));
                        coin--;
                        flag = true;
                        break;
                    }
                }
            }
            
            if (!flag && coin >= 2) {
                // 3-2. additionalCardSet에서 2개
                for (int card : additionalCardSet) {
                    if (additionalCardSet.contains(n + 1 - card)) {
                        additionalCardSet.remove((Object) card);
                        additionalCardSet.remove((Object) (n + 1 - card));
                        coin -= 2;
                        flag = true;
                        break;
                    }
                }
            }
            
            // n + 1에 맞춰서 카드를 낼 수 없는 경우 -> 끝내기
            if (!flag) {
                break;
            }
        }
        
        return answer;
    }
}