[코딩테스트] 2024 KAKAO WINTER INTERNSHIP - n + 1 카드게임 (Javascript)

코드

function solution(coin, cards) {
  const n = cards.length;
  let round = 1;
  let end = n / 3 + 1;
  let gaveCards = new Array(n).fill(false);
  while (true) {
    let isPossibleNextRound = false;
    for (let i = 0; i < end; i++) {
      if (gaveCards[i]) continue;
      for (let j = i + 1; j <= end; j++) {
        if (cards[i] + cards[j] === n + 1) {
          const requiredCoins = (i >= n / 3 ? 1 : 0) + (j >= n / 3 ? 1 : 0);
          if (coin < requiredCoins) break;
          coin -= requiredCoins;
          gaveCards[i] = true;
          gaveCards[j] = true;
          isPossibleNextRound = true;
          round += 1;
          end += 2;

          break;
        }
      }
      if (isPossibleNextRound || end >= n) break;
    }
    if (!isPossibleNextRound || end >= n) break;
  }
  return round;
}

접근 방식

n의 크기가 작기 때문에 완전 탐색으로 문제를 해결하기로 했다!

먼저, end라는 변수에 1라운드에서 뽑을 수 있는 마지막 카드의 인덱스를 저장했다.
이 end 변수는 라운드가 증가할 때마다 2씩 증가한다.
이는 매 라운드마다 뽑을 수 있는 카드의 수가 2장씩 증가하기 때문이다.

gaveCards라는 배열은 cards 배열에 있는 카드가 현재 사용된 카드인지 여부를 저장하는 배열이다.
인덱스에 해당하는 카드가 사용되었으면 true, 그렇지 않으면 false로 설정된다.
이를 통해 아직 사용되지 않은 카드를 대상으로 두 장씩 더해보면서, 그 합이 n + 1이 되는지 확인한다.

각 카드의 인덱스가 n/3 이상인 경우, 해당 카드를 내기 위해 1개의 코인이 필요하다.
즉, a 카드와 b 카드가 모두 n/3 이상인 경우, 총 2개의 코인이 필요하다.

다음으로, 현재 보유한 코인의 개수가 총 필요한 코인의 개수 이상인지를 확인한다.
만약 충분하다면 해당 카드를 내고 다음 라운드로 넘어간다.
그렇지 않다면, 2차 반복문을 break하고, 1차 반복문을 계속 진행하여 다른 가능한 카드 조합을 시도한다.

코인의 개수가 현재 필요한 코인 개수보다 적더라도, 다음 1차 반복문의 카드와 2차 반복문의 카드 조합에서 필요한 코인 개수가 현재 가지고 있는 코인 개수보다 적을 수 있기 때문에 while 문을 종료하지 않고 계속해서 탐색을 진행한다.