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

문제 링크

---

프로그래머스

접근 방법

---

카드 x가 있을 때 필요한 짝은 항상 n + 1 - x로 정해집니다.
따라서 모든 조합을 탐색하지 않고, HashSet을 이용해 필요한 카드가 있는지만 확인하면 됩니다.

소스 코드

---

import java.util.*;

class Solution {
    int target;

    private boolean usePair(Set<Integer> set1, Set<Integer> set2) {
        int a = -1, b = -1;

        for (int card : set1) {
            b = target - card;

            if (set2.contains(b)) {
                a = card;
                break;
            }
        }

        if (a == -1) {
            return false;
        }

        set1.remove(a);
        set2.remove(b);

        return true;
    }

    public int solution(int coin, int[] cards) {
        int n = cards.length, idx = 0 ,round = 1;
        target = n + 1;

        Set<Integer> hand = new HashSet<>(), draw = new HashSet<>();

        while (idx < n / 3) {
            hand.add(cards[idx++]);
        }

        while (idx < n) {
            draw.add(cards[idx++]);
            draw.add(cards[idx++]);

            if (usePair(hand, hand)) {
                round++;
            } else if (coin >= 1 && usePair(hand, draw)) {
                coin--;
                round++;
            } else if (coin >= 2 && usePair(draw, draw)) {
                coin -= 2;
                round++;
            } else {
                break;
            }
        }

        return round;
    }
}

코드 설명

---

target은 매 라운드에 내야 하는 카드 2장의 합인 n + 1을 저장합니다.

hand는 처음부터 가지고 시작하는 n / 3개의 카드를 저장합니다.
draw는 라운드가 진행되면서 뽑은 카드들을 저장합니다.

usePair() 메서드는 두 개의 Set에서 합이 target이 되는 카드 쌍을 찾습니다.
그 후 hand + hand, hand + draw, draw + draw 순서로 가능한 쌍을 확인합니다.

hand + hand는 코인을 쓰지 않고 라운드를 넘길 수 있으므로 가장 먼저 확인합니다.
hand + draw는 뽑은 카드 1장을 가져와야 하므로 코인 1개를 사용합니다.
draw + draw는 뽑은 카드 2장을 모두 가져와야 하므로 코인 2개를 사용합니다.

세 경우 모두 불가능하면 더 이상 다음 라운드로 갈 수 없으므로 반복문을 종료합니다.

시간 초과 (재귀)

---

import java.util.*;
import java.io.*;

class Solution {
    
    List<Integer> myCard = new ArrayList<>();
    int[] card;
    int max = 0, n;
    
    void recursive(int coin, int idx, int round) {
        if (idx == n) {
            max = round;
            return;
        }
        
        List<int[]> pair = new ArrayList<>();

        for (int i = 0; i < myCard.size(); i++) {
            for (int j = i + 1; j < myCard.size(); j++) {
                if (myCard.get(i) + myCard.get(j) == n + 1) {
                    pair.add(new int[]{i, j});
                }
            }
        }
        int size = pair.size();
        
        // 1개 선택
        if (coin > 0) {
            myCard.add(card[idx]); // 첫번째 카드 선택
            for (int i = 0; i < myCard.size() - 1; i++) {
                if (myCard.get(i) + myCard.get(myCard.size() - 1) == n + 1) {
                    pair.add(new int[]{i, myCard.size() - 1});
                }
            }
            
            for (int[] tmp : pair) {
                int a = myCard.get(tmp[0]),  b = myCard.get(tmp[1]);
                myCard.remove(tmp[1]);
                myCard.remove(tmp[0]);
                
                recursive(coin - 1, idx + 2, round + 1);
                
                myCard.add(tmp[0], a);
                myCard.add(tmp[1], b);
            }
            
            myCard.remove(myCard.size() - 1);
            while (pair.size() > size) {
                pair.remove(pair.size() - 1);
            }
            
            myCard.add(card[idx + 1]); // 두번째 카드 선택
            for (int i = 0; i < myCard.size() - 1; i++) {
                if (myCard.get(i) + myCard.get(myCard.size() - 1) == n + 1) {
                    pair.add(new int[]{i, myCard.size() - 1});
                }
            }
            
            for (int[] tmp : pair) {
                int a = myCard.get(tmp[0]),  b = myCard.get(tmp[1]);
                myCard.remove(tmp[1]);
                myCard.remove(tmp[0]);
                
                recursive(coin - 1, idx + 2, round + 1);
                
                myCard.add(tmp[0], a);
                myCard.add(tmp[1], b);
            }
            
            myCard.remove(myCard.size() - 1);
            while (pair.size() > size) {
                pair.remove(pair.size() - 1);
            }
        }
        
        // 2개 선택
        if (coin > 1) {
            myCard.add(card[idx]);
            myCard.add(card[idx + 1]);
            for (int i = 1; i <= 2; i++) {
                for (int j = 0; j < myCard.size() - i; j++) {
                    if (myCard.get(j) + myCard.get(myCard.size() - i) == n + 1) {
                        pair.add(new int[]{j, myCard.size() - i});
                    }
                }
            }
            
            for (int[] tmp : pair) {
                int a = myCard.get(tmp[0]),  b = myCard.get(tmp[1]);
                myCard.remove(tmp[1]);
                myCard.remove(tmp[0]);
                
                recursive(coin - 2, idx + 2, round + 1);
                
                myCard.add(tmp[0], a);
                myCard.add(tmp[1], b);
            }
            
            myCard.remove(myCard.size() - 1);
            myCard.remove(myCard.size() - 1);
            while (pair.size() > size) {
                pair.remove(pair.size() - 1);
            }
        }
        
        // 다 버리기

        for (int[] tmp : pair) {
            int a = myCard.get(tmp[0]),  b = myCard.get(tmp[1]);
            myCard.remove(tmp[1]);
            myCard.remove(tmp[0]);

            recursive(coin, idx + 2, round + 1);

            myCard.add(tmp[0], a);
            myCard.add(tmp[1], b);
        }
        
        
        max = Integer.max(max, round);
    }
    
    
    public int solution(int coin, int[] cards) {
        
        n = cards.length;
        int startIdx = cards.length / 3;
        card = cards;
        for (int i = 0; i < startIdx; i++) {
            myCard.add(cards[i]);
        }

        
        recursive(coin, startIdx, 1);
        return max;
    }
}