[JAVA] 프로그래머스 (Lv.3) n + 1 카드게임

링크

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

---

입력 예제

int coin = 4
int[] cards = [3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4]

---

출력 예제

int result = 5

---

풀이

두 카드의 합이 n+1이 되도록 하는 최적의 선택을 하는 그리디 문제이다. 이 문제를 백트래킹으로 진행한다면 우선 2가지의 카드를 뽑거나 버리는 경우의 수는 4, 그리고 최악의 경우 $O(n/2)$만큼 라운드가 진행되므로 완전 탐색을 진행한다면 $O(4^{n/2})$이 되므로 기하급수적으로 커진다.

게임이 종료되는 조건은 다음과 같다.

• n+1이 되는 카드쌍이 존재하지 않을 경우
• 들고 있는 카드가 없을 경우
• 동전의 개수가 0 미만일 경우 (새로운 카드를 뽑아야 카드쌍 존재)

우선 n/3장의 카드를 순서대로 뽑고 게임을 진행한다.

//처음 카드 뽑기
for (int i = 0; i < n / 3; i++) {
    cardList.add(cards[i]);
}

카드쌍을 만족하는 카드는 불리언 배열로 체크한다. 매 라운드 마다 카드를 뽑기전 현재 들고있는 카드 중에 카드쌍을 만족하는 카드가 있는지 확인한다.

//카드를 뽑기 전 합이 n+1이 되는 카드쌍 존재 여부
for (int i = 0; i < n / 3; i++) {
    for (int j = i + 1; j < n / 3; j++) {
        if (cardList.get(i) + cardList.get(j) == n + 1 && !paired[i] && !paired[j]) {
            paired[i] = true;
            paired[j] = true;
            return true;
        }
    }
}

없다면 뽑은 카드까지 추가하여 카드쌍인 존재하는지 확인하고, 존재하면 뽑힌 카드에 대해서 동전을 소모한다.

//뽑은 카드를 포함하여 합이 n+1이 되는 카드쌍 존재 여부
for (int i = 0; i <= cardList.size(); i++) {
    for (int j = i + 1; j < cardList.size(); j++) {
        if (cardList.get(i) + cardList.get(j) == n + 1 && !paired[i] && !paired[j]) {
            paired[i] = true;
            paired[j] = true;
            
            //뽑은 카드일 경우 동전 소모
            if (i >= n / 3) {
                myCoin--;
            }
            if (j >= n / 3) {
                myCoin--;
            }
            
            return true;
        }
    }
}

이런식으로 마지막 카드를 카드를 뽑을 때까지 반복하면서 게임이 종료될 때까지 반복한다.

//라운드 진행
for (int i = n / 3; i < n; i += 2) {
	//카드 2장을 뽑음
    cardList.add(cards[i]);
    cardList.add(cards[i + 1]);
    
    if (!canPlay()) {  //n+1이 되는 카드쌍이 존재하지 않으면 게임 종료
        return round;
    }
    
    if (myCoin < 0) {  //동전이 0보다 작아지면 종료
        return round;
    }
    
    round++;
}

전체 코드

import java.util.ArrayList;
import java.util.List;

/*
프로그래머스 / n + 1 카드게임 / Level 3
https://school.programmers.co.kr/learn/courses/30/lessons/258707
 */
class Solution {

    private static List<Integer> cardList = new ArrayList<>();
    private static boolean[] paired;
    private static int n, myCoin;

    public int solution(int coin, int[] cards) {
        n = cards.length;
        myCoin = coin;
        paired = new boolean[n];

        //처음 카드 뽑기
        for (int i = 0; i < n / 3; i++) {
            cardList.add(cards[i]);
        }

        int round = 1;

        //라운드 진행
        for (int i = n / 3; i < n; i += 2) {
            cardList.add(cards[i]);
            cardList.add(cards[i + 1]);

            if (!canPlay()) {  //n+1이 되는 카드쌍이 존재하지 않으면 게임 종료
                return round;
            }

            if (myCoin < 0) {  //동전이 0보다 작아지면 종료
                return round;
            }

            round++;
        }

        return round;
    }

    private static boolean canPlay() {
        //카드를 뽑기 전 합이 n+1이 되는 카드쌍 존재 여부
        for (int i = 0; i < n / 3; i++) {
            for (int j = i + 1; j < n / 3; j++) {
                if (cardList.get(i) + cardList.get(j) == n + 1 && !paired[i] && !paired[j]) {
                    paired[i] = true;
                    paired[j] = true;
                    return true;
                }
            }
        }

        //뽑은 카드를 포함하여 합이 n+1이 되는 카드쌍 존재 여부
        for (int i = 0; i <= cardList.size(); i++) {
            for (int j = i + 1; j < cardList.size(); j++) {
                if (cardList.get(i) + cardList.get(j) == n + 1 && !paired[i] && !paired[j]) {
                    paired[i] = true;
                    paired[j] = true;

                    //뽑은 카드일 경우 동전 소모
                    if (i >= n / 3) {
                        myCoin--;
                    }
                    if (j >= n / 3) {
                        myCoin--;
                    }

                    return true;
                }
            }
        }

        return false;  //존재하지 않으면 게임 종료
    }
}