[programmers/js] n + 1 카드게임

n + 1 카드게임

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

문제 설명

당신은 1~n 사이의 수가 적힌 카드가 하나씩 있는 카드 뭉치와 동전 coin개를 이용한 게임을 하려고 합니다. 카드 뭉치에서 카드를 뽑는 순서가 정해져 있으며, 게임은 다음과 같이 진행합니다.

게임 순서
0. 사용자는 카드 뭉치(n개)와 동전 coin개를 가지고 시작합니다.
1. 카드 뭉치(cards)에서 카드 n/3장을 뽑아 가집니다. (n은 6의 배수)
2. 각 라운드가 시작할 때 카드를 순서대로 2장 뽑습니다.
2-1. 사용자는 뽑은 카드를 coin을 소모해 가져올지 결정할 수 있습니다.
3. 합이 N + 1이 되는 카드 2장을 선택해 제출합니다.

만약 N + 1 되는 카드가 없거나, 더이상 뽑을 카드가 없는 최대 round를 반환합니다.

풀이

우선 keep 집합을 생성해 기존에 뽑은 카드 중 사용하지 않은 카드를 보관합니다. 각 숫자는 한 번만 등장하므로, Set을 활용하면 빠르게 조회 가능합니다.

다음은 코인 사용 방법입니다.
문제의 코인 사용 방법은 총 3개의 경우만 존재합니다.

1. 현재 손에 있는 카드 2장으로 N+1을 만들면 코인 없이 사용
2. 현재 손패 1장 + 이번에 뽑은 카드 1장으로 N+1을 만들면 코인 1개 사용
3. 기존 keep에서 2장을 사용해 N+1을 만들면 코인 2개 사용
4. 위 방법이 모두 불가능하면 더 이상 진행할 수 없으면 게임 종료

위 처럼 코인을 적게 사용하는 조건부터 검색해 문제를 해결할 수 있습니다.

function solution(coin, cards) {
    const N = cards.length;
    const target = N + 1;
    let nowI = N / 3;  // 현재 뽑은 카드 위치
    let round = 0;  // 진행된 라운드 수
    
    // 손에 들고 있는 카드 (Set 사용)
    const hand = new Set(cards.slice(0, nowI));
    const keep = new Set();
    
    while (true) {
        round += 1;
        // 남은 카드가 없으면 종료
        if (nowI >= N) return round;

        // 새로 뽑은 카드 2장
        const card1 = cards[nowI], card2 = cards[nowI + 1];
        keep.add(card1)
        keep.add(card2)
        
        nowI += 2;
        let found = false;

        // 현재 손에 있는 카드 두 장으로 N+1을 만들 수 있는지 확인 (코인 0개)
        for (const num of hand) {
            if (hand.has(target - num)) {
                hand.delete(num);
                hand.delete(target - num);
                found = true;
                break;  // 찾으면 즉시 종료
            }
        }
        if (found) continue;

        // 현재 카드 1장 + 새로 뽑은 카드 1장으로 N+1을 만들기 (코인 1개 사용)
        for (const num of hand) {
            if (keep.has(target - num) && coin > 0) {
                coin -= 1;
                hand.delete(num);
                keep.delete(target - num);
                found = true;
                break;  // 찾으면 즉시 종료
            }
        }
        if (found && coin > 0) continue;

        // 뽑은 카드 2장으로 N+1을 만들 수 있는지 확인 (코인 2개 사용)
        for (const num of keep) {
            if (keep.has(target - num) && coin > 1) {
                coin -= 2;
                keep.delete(num);
                keep.delete(target - num);
                found = true;
                break;  // 찾으면 즉시 종료
            }
        }
        
        // 더 이상 조합을 만들 수 없으면 종료
        if (!found) return round;
    }
}