문제

Programmers Lv3, n + 1 카드게임

핵심

• n개의 카드로 이루어진 카드 뭉치와 여러 코인이 주어진다. 아래 규칙에 따라 진행된다.
  • 처음에 카드 뭉치에서 카드 n/3장을 뽑아 모두 가집니다. (n은 6의 배수입니다.) 당신은 카드와 교환 가능한 동전 coin개를 가지고 있습니다.
  • 게임은 1라운드부터 시작되며, 각 라운드가 시작할 때 카드를 두 장 뽑습니다. 카드 뭉치에 남은 카드가 없다면 게임을 종료합니다. 뽑은 카드는 카드 한 장당 동전 하나를 소모해 가지거나, 동전을 소모하지 않고 버릴 수 있습니다.
  • 카드에 적힌 수의 합이 n+1이 되도록 카드 두 장을 내고 다음 라운드로 진행할 수 있습니다. 만약 카드 두 장을 낼 수 없다면 게임을 종료합니다.
• 위 규칙을 적용하며 최대 진행할 수 있는 라운드를 구하면 된다.

DFS (시간 초과)

• 가장 직관적으로 접근할 수 있는 풀이다. 라운드마다 4가지 경우를 선택할 수 있다.
  • 왼쪽 카드를, 코인을 사용해 갖기
  • 오른쪽 카드를, 코인을 사용해 갖기
  • 둘 다 갖기
  • 둘 다 갖지 않기
• n이 최대 999개일 떄, 라운드가 최대 666번 진행한다. 한 라운드마다 4번의 경우가 있으므로 $4^{666}$ 경우의 수가 나온다. 가지치기 하더라도, 워낙 경우가 많기 때문에 시간 초과라고 판단하였다.

Greedy

• 모든 경우를 탐색하는 건 위에서 살펴본 것처럼 매우 많은 경우가 나온다. 매 순간 최적의 선택을 하는 그리디 알고리즘을 적용해 볼 수 있다. 코인을 최대한 사용하지 않으면서, 두 카드를 이용해 n+1 숫자를 만들 수 없을 때 코인을 사용하면 되지 않을까? 효율적으로 코인을 사용하기 위해 코인 하나만 사용하여 (n + 1 - 기존 가지고 있는 카드번호)인 카드를 카드 더미에서 찾아볼 수 있다. 카드 더미에서 찾을 수 없다면, 이번에는 코인 2개를 사용하여 카드 더미에서 2개를 골라 n+1 숫자를 만들 수 있는지 찾는다. n+1 숫자를 만들 수 없을 때까지 진행하면 최대 가능한 라운드를 구할 수 있다.
• 구체적인 코드 작성 과정은 다음과 같다.
  1. 처음에 n/3 장을 손에 가진다.
  2. 손에 있는 카드 중 두 장이 target(n+1)이 되는지 확인 (List hand)
  3. 라운드마다 2개의 카드를 카드 더미에 카드 추가 (List cardStack)
  4. target이 되지 않는다면
  • 4-1: (target - 손에 있는 카드 숫자)가 카드 더미에 있는지 확인한다. (코인으로 카드 한 장)
  • 4-1: 4-1에서 카드가 없다면 카드 더미에서 코인 2개를 사용해 target을 만들 수 있는지 확인한다. (코인으로 카드 두 장)
• 손 또는 카드더미에서 카드 두 장을 골라 target을 만드는지 검사하는 로직은 아래와 같이 작성할 수 있다. 주의할 점은 가장 큰 인덱스부터 제거해야 한다. 작은 거 부터 제거하면, 큰 인덱스를 제거할 때 전체 배열의 크기가 작아진 상태이므로 OutOfBound가 발생할 수 있기 때문이다.

boolean search(List<Integer> list, int target) {
	for (int i = 0; i < list.size(); ++i) {
		for (int j = i + 1; j < list.size(); ++j) {
			if (list.get(i) + list.get(j) == target) {
				list.remove(j);
				list.remove(i);
				return true;
			}
		}
	}
	return false;
}

• 놓치기 쉬운 테스트 케이스가 존재한다. 현재 로직에선 target을 만들 수 있다면, 계속해서 라운드를 증가시킨다. 특정 케이스에서 최대 가능한 라운드보다 더 커질 수 있다. 따라서 정답을 구할 때 최대 라운드에 도달했다면 더 이상 카드를 탐색하지 않는다.

while (true) {
  if (ans == n / 3 + 1) break; // 최대 라운드 도달 시 종료
  
  if (isSearched) ++ans; // 찾았다면 다음 라운드로, 못 찾았다면 종료
  else break;
}

개선

시간복잡도

• $O(n^3)$
  

코드

import java.util.*;

class Solution {
    public int solution(int coin, int[] cards) {
        int n = cards.length;
        
        int target = n + 1;
        List<Integer> cardStack = new ArrayList<>();
        List<Integer> hand = new ArrayList<>();
        for (int i = 0; i < n / 3; ++i) hand.add(cards[i]);
        
        int cursor = n / 3; 
        int ans = 1;
        while (true) {
            if (ans == n / 3 + 1) break;
            if (cursor < n) cardStack.add(cards[cursor++]);
            if (cursor < n) cardStack.add(cards[cursor++]);

            boolean isSearched = search(hand, target);
  
            if (!isSearched && coin > 0) {
                for (int i = 0; i < hand.size(); i++) {
                    int find = target - hand.get(i);
                    if (cardStack.contains(find)) {
                        cardStack.remove(Integer.valueOf(find));
                        coin--;
                        isSearched = true;
                        break;
                    }
                }
            }  
  
            if (!isSearched && coin >= 2) {
                isSearched = search(cardStack, target);
                if (isSearched) {
                    coin -= 2;
                }
            }
            
            if (isSearched) ++ans;
            else break;
        }

        return ans;
    }

    boolean search(List<Integer> list, int target) {
        for (int i = 0; i < list.size(); ++i) {
            for (int j = i + 1; j < list.size(); ++j) {
                if (list.get(i) + list.get(j) == target) {
                    list.remove(j);
                    list.remove(i);
                    return true;
                }
            }
        }
        return false;
    }
}