[2024 카카오] n + 1 카드게임 JS

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

 

문제 설명

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

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

예를 들어 n = 12, coin = 4이고 [3, 6, 7, 2, 1, 10, 5, 9, 8, 12, 11, 4] 순서대로 카드를 뽑도록 카드 뭉치가 섞여 있습니다.

처음에 3, 6, 7, 2 카드 4장(= n/3)과 동전 4개(= coin)를 가지고 시작합니다. 다음 라운드로 진행하기 위해 내야 할 카드 두 장에 적힌 수의 합은 13(= n+1)입니다. 다음과 같은 방법으로 최대 5라운드까지 도달할 수 있습니다.

1. 1라운드에서 뽑은 카드 1, 10을 동전 두 개를 소모해서 모두 가집니다. 카드 3, 10을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 1, 2, 6, 7이고 동전이 2개 남습니다.
2. 2라운드에서 뽑은 카드 5, 9를 동전을 소모하지 않고 모두 버립니다. 카드 6, 7을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 1, 2고 동전이 2개 남습니다.
3. 3라운드에서 뽑은 카드 8, 12 중 동전 한 개를 소모해서 카드 12를 가집니다. 카드 1, 12을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 2이고 동전이 1개 남습니다.
4. 4라운드에서 뽑은 카드 11, 4 중 동전 한 개를 소모해서 카드 11을 가집니다. 카드 2, 11을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드와 동전은 없습니다.
5. 5라운드에서 카드 뭉치에 남은 카드가 없으므로 게임을 종료합니다.

처음에 가진 동전수를 나타내는 정수 coin과 카드를 뽑는 순서대로 카드에 적힌 수를 담은 1차원 정수 배열 cards가 매개변수로 주어질 때, 게임에서 도달 가능한 최대 라운드의 수를 return 하도록 solution 함수를 완성해 주세요.

---

제한사항

• 0 ≤ coin ≤ n
• 6 ≤ cards의 길이 = n < 1,000
  • cards[i]는 i+1번째로 뽑는 카드에 적힌 수를 나타냅니다.
  • 1 ≤ cards[i] ≤ n
  • cards의 원소는 중복되지 않습니다.
• n은 6의 배수입니다.

 

 

입출력 예 설명

입출력 예 #1

문제 예시와 같습니다.

입출력 예 #2

처음에 1, 2, 3, 4 카드 4장과 동전 3개를 가지고 시작합니다. 다음 라운드로 진행하기 위해 내야 할 카드 두 장에 적힌 수의 합은 13입니다. 다음과 같은 방법으로 최대 2라운드까지 도달할 수 있습니다.

1. 1라운드에서 뽑은 카드 5, 8을 동전 두 개를 소모해서 모두 가집니다. 카드 5, 8을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 1, 2, 3, 4이고 동전이 1개 남습니다.
2. 2라운드에서 뽑은 카드 6, 7중 남은 동전 한 개로 어떤 카드를 골라도 카드에 적힌 수의 합이 13이 되도록 카드 두 장을 낼 수 없으므로 게임이 종료됩니다.

따라서 2를 return 하면 됩니다.

입출력 예 #3

처음에 5, 8, 1, 2 카드 4장과 동전 2개를 가지고 시작합니다. 다음 라운드로 진행하기 위해 내야 할 카드 두 장에 적힌 수의 합은 13입니다. 다음과 같은 방법으로 최대 4라운드까지 도달할 수 있습니다.

1. 1라운드에서 뽑은 카드 9, 4를 동전을 소모하지 않고 모두 버립니다. 카드 5, 8을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 1, 2고 동전이 2개 남습니다.
2. 2라운드에서 뽑은 카드 12, 11를 동전 두 개를 소모해서 모두 가집니다. 카드 1, 12를 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드는 2, 11이고 남은 동전이 없으므로 더 이상 카드를 추가로 가질 수 없습니다.
3. 3라운드에서 뽑은 카드 3, 10을 모두 버립니다. 카드 2, 11을 내고 다음 라운드로 진행합니다. 이때 손에 남은 카드와 동전은 없습니다.
4. 4라운드에서 뽑은 카드 6, 7을 모두 버립니다. 카드에 적힌 수의 합이 13이 되도록 카드 두 장을 낼 수 없으므로 게임이 종료됩니다.

따라서 4를 return 하면 됩니다.

입출력 예 #4

처음에 1, 2, 3, 4, 5, 6 카드 6장과 동전 10개를 가지고 시작합니다. 다음 라운드로 진행하기 위해 내야 할 카드 두 장에 적힌 수의 합은 19입니다. 1라운드에서 카드 7, 8 두 장을 모두 가져도 합이 19가 되도록 카드 두 장을 낼 수 없으므로 최대 1라운드까지만 도달할 수 있습니다.

따라서 1을 return 하면 됩니다.

 

---

 

문제 요점

• 1~n개의 숫자가 하나씩 있는 카드뭉치, 카드를 뽑는 순서는 정해졌다, 카드는 중복되지 않는다
  처음에 n/3장을 뽑아 가진다
• 매 라운드마다 새로운 2장을 뽑는다, 카드뭉치에 남은 카드가 없으면 종료한다
• 뽑은 카드 1장은 coin 하나를 소모해서 사거나 / 돈을 소모하지 않고 그냥 버릴 수 있다.
• 합이 n+1가 되는 2장의 카드를 제출해야 다음 라운드로 진행할 수 있다.
• 도달 가능한 최대 라운드를 구해라

즉 정리하자면 

종료하는 조건

• 남은 카드가 없을 시
• n+1을 못 만들 시

다음 라운드로 가는 조건

• n+1을 만들어 제출

 

풀이

혼자서 생각하다가 언제 코인을 사용할지에서 막혀서 카카오 답을 참고했다.

 

 

풀이를 읽고 내가 생각한 키포인트는 

매 라운드마다 뽑은 카드를 바로 사용할지 판단하는게 아니라
기억해두었다가 미래에 필요할 때 사용하고 coin도 그 때 지불하면 되는것이다

 

미래에 필요할 때 지불하면 되므로 동전은 최대한 아끼고 아껴서 최장 라운드까지 끌고 가야한다.

따라서 동전을 가장 적게 사용하는 방법을 우선적으로 찾아서 라운드를 진행한다

 

예를 들어 원래 손에 갖고 있는 카드들의 배열을 hand, 라운드마다 뽑은 카드를 기록하는 keep배열을 뒀을 때,

위에서 말했듯이 다음과 같은 순으로 라운드를 통과한다.

• 동전 0개를 소모하는 방법: hand의 2장으로 n+1을 만들 수 있는 경우
• 동전 1개를 소모하는 방법: hand의 1장과 keep 1장의 합이 n+1 이 되는 경우
• 동전 2개를 소모하는 방법: keep의 2장의 합이 n+1이 되는 경우

 

하지만 위와 같은 방법으로도 n+1을 만들 수 없거나, 카드를 이미 다 뽑았으면 바로 게임을 종료한다.

 

 

전체코드

 

function solution(coin, cards) {
  const target = cards.length + 1;
  let hand = cards.splice(0, cards.length / 3); // 손에 갖고 있는 카드배열
  let keep = []; // 매 라운드마다 뽑는 카드를 기억하는 배열
  let round = 0;

  // 남은 카드가 없을 때까지 진행
  while (cards.length) {
    // 이번 라운드에 뽑은 2장을 기억한다
    const picked = cards.splice(0, 2);
    picked.forEach((e) => keep.push(e));

    // 손에 갖고 있던 것 2장으로 만들 수 있는지 확인
    const handPair = getPair(hand, target);
    // 만들 수 있으면
    if (handPair) {
      hand = hand.filter((e) => !handPair.includes(e)); // hand에서 사용한 카드 삭제
      round++; // 라운드 증가
      continue;
    }

    // 손에 카드 1개 keep 1개로 만들 수 있는지 확인
    const handKeepPair = getHandKeepPair(hand, keep, target);
    // 만들 수 있고 동전도 있다면
    if (handKeepPair && coin) {
      const [handNum, keepNum] = handKeepPair;
      hand = hand.filter((e) => e !== handNum); // hand에서 사용한 카드 삭제
      keep = keep.filter((e) => e !== keepNum); // keep에서 사용한 카드 삭제
      coin--; // keep에서 하나 구매한 동전 감소
      round++;
      continue;
    }

    // keep2개로 만들 수 있는지 확인
    const keepPair = getPair(keep, target);
    // 만들 수 있고 동전이 2개 이상이면
    if (keepPair && coin >= 2) {
      keep = keep.filter((e) => !keepPair.includes(e)); // 사용한 keep 숫자 삭제
      coin -= 2; // 사용한 2개 동전 감소
      round++;
      continue;
    }
    // 위의 3가지 방법으로 target을 만들 수 없으면 게임종료
    break;
  }
  return round + 1; // +1은 마지막 라운드를 통과했으므로 +1
}

// arr에서 2장을 골라 target을 만들 수 있는지 확인하는 함수
function getPair(arr, target) {
  for (let i = 0; i < arr.length - 1; i++) {
    const first = arr[i];
    for (let j = i + 1; j < arr.length; j++) {
      const second = arr[j];
      if (first + second === target) {
        return [first, second];
      }
    }
  }
  return null;
}

// hand에서 1장, keep에서 1장으로 target을 만들 수 있는지 확인하는 함수
function getHandKeepPair(hand, keep, target) {
  for (let i = 0; i < hand.length; i++) {
    const first = hand[i];
    for (let j = 0; j < keep.length; j++) {
      const second = keep[j];
      if (first + second === target) {
        return [first, second];
      }
    }
  }
  return null;
}