[JavaScript] Programmers n+1카드 게임 (JS)

n + 1 카드 게임

📚 문제 설명

1 ~ n 사이의 숫자가 적혀있는 카드 뭉치 cards와 동전 coin개가 있다.

이 카드와 동전을 가지고 게임을 진행하는데 게임은 아래와 같은 과정으로 진행된다.

• 게임 시작시 cards / 3 의 카드가 주어진다.
• 내가 가지고 있는 카드 2장의 숫자를 합쳐 n + 1을 만들면 다음 라운드로 넘어간다.
• 매 라운드마다 cards 에서 2장의 카드를 뽑는다.
  • 2장 뽑은 카드은 coin을 써서 내가 가질 수 있고, coin을 써서 가진 그 카드를 이용해 n + 1을 만들어도 된다.

👨🏻‍💻 풀이 과정

이 문제를 풀 때 가장 중요한 부분은 매 라운드 2장씩 뽑는 카드 중에 어떤 카드를 coin을 사용해 가져올지이다.

만약 각각의 라운드에 뽑은 2장을 카드만 보고 판단을 내리면 미래에 쓸 카드를 미리 뽑는 경우를 계산하지 못하게 된다.
따라서 keep 배열을 이용해 현재 라운드까지 뽑았던 모든 카드를 저장하여, 현재 라운드에 만약 사용해야 한다면,
keep 배열에서 제거하면 된다.

전체적인 로직은 아래와 같다.

• 처음 손에 주어진 카드를 hand 변수에 저장.
• 반복문을 통해 매 라운드 진행.
  • keep에 2장의 카드를 추가.
  • hand에 있는 숫자만으로 만들 수 있으면
    • hand에서 숫자 제거.
    • round + 1
  • hand 1개 + keep 1개 로 만들어지면
    • hand 와 keep 에서 숫자 제거.
    • round + 1
    • coin - 1
  • keep 2개로 만들어지면
    • keep에서 숫자 제거.
    • round + 1
    • coin - 1
• 정답 출력.

전체 풀이

function solution(coin, cards) {
	// 매 라운드 2장의 카드를 뽑아 저장할 배열.
    let keep = [];
  	// 만들 숫자.
    const target = cards.length + 1;
  	// 초기 손패.
    let hand = cards.splice(0, cards.length / 3);;
  	// 라운드.
    let round = 0;

  	// 1개의 동전을 이용하는 경우를 계산할 함수.
    const BuyOne = (inMyHand, MyKeep) => {
        for (let i = 0; i < inMyHand.length; i++) {
            for (let j = 0; j < MyKeep.length; j++) {
                if (inMyHand[i] + MyKeep[j] === target) {
                    inMyHand.splice(i, 1);
                    MyKeep.splice(j, 1);
                    return [inMyHand, MyKeep];
                }
            }
        }
        return null;
    };
	// 2개의 동전을 이용해 keep 배열에서 카드를 골라 계산할 함수.
    const BuyTwo = (MyKeep) => {
        for (let i = 0; i < MyKeep.length - 1; i++) {
            for (let j = 1; j < MyKeep.length; j++) {
                if (MyKeep[i] + MyKeep[j] === target) {
                    const A = MyKeep[i];
                    const B = MyKeep[j];
                    return MyKeep.filter(v => {
                        if (v !== A && v !== B) {
                            return true;
                        }
                    });
                }
            }
        }
        return null;
    };
  
  	// 반복문 시작.
    while (cards.length) {
      	// 2장의 카드를 뽑아서 keep 배열에 추가.
        cards.splice(0, 2).forEach(v => keep.push(v));
      	// 손에 있는 카드로만 만들 경우.
      	// 이미 있던 함수를 이용 (BuyTwo함수)
        const ResultOne = BuyTwo(hand);
      	// 만약 손패에 카드가 있고, 숫자를 만들 수 있다면,
        if (hand.length && ResultOne) {
            hand = ResultOne;
            round++;
            continue;
        }

      	// 1장의 카드를 사서 만들 경우.
        const ResultTwo = BuyOne(hand, keep);
		// 만약 만들 수 있고, 동전이 있다면
        if (ResultTwo && coin) {
            hand = ResultTwo[0];
            keep = ResultTwo[1];
            coin -= 1;
            round++;
            continue;
        }

      	// 2장의 카드를 사서 만들 경우.
        const ResultThird = BuyTwo(keep);
		// 동전이 2장 이상 있고, 만들 수 있다면
        if (ResultThird && coin >= 2) {
            keep = ResultThird;
            round++;
            coin -= 2;
            continue;
        }
      	// 만약 만들 수 없다면, 종료.
        break;
    }
	// 마지막 실패에도 라운드가 증가해야한다.
    return round + 1;
}

🧐 후기

도저히 미래에 쓸 동전을 어떻게 계산할지 생각이 나지 않아서 풀이를 참고했다.
keep 배열을 사용할 생각만 한다면 그 후로는 쭉쭉 풀렸던 문제였다.