[JS] n+1 카드게임

 

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

프로그래머스

 

 

2024 카카오 인턴 문제로 추가된 따끈따끈한 문제로 구현능력을 보는 문제같았다.

 

제한사항을 보면 알겠지만 케이스가 널널한 편이다.

 

 

우선 문제를 해결하기 전에 n+1을 만들기 위해선 항상 수가 쌍으로 존재한다는 생각을 해야한다.

 

테스트 케이스들에서 n이 12로 고정되었는데 n+1인 13을 만들기 위해서는

(1,12) (2,11) (3,10) ... 이런식으로 두 수로 n+1을 만들기 위해서는 한가지의 쌍만 존재한다는 것을 활용할 수 있다.

 

즉 n/2 크기의 배열을 활용해서 해당 문제를 해결하였다. 이 배열의 이름을 memo라고 하자.

 

이제 첫번째 케이스를 적용해보며 풀이 방법을 이해해보자.

n이 12라면 memo의 크기는 6이 되는데 숫자가 1부터 시작하므로 memo의 크기를 7로 두었다.

 

memo -> [0,0,0,0,0,0,0]

그리고 n/3까지의 카드를 등록해야 한다.

memo -> [0,0,1,1,0,0,2]

 

그리고 해당 배열을 복사한 initialMemo 배열을 만든다. 이건 후에 알아보자.

 

able이란 배열을 활용해서 현재 n+1을 만들 쌍이 있는지 없는지 관리하자.

able안에는 배열이 들어가며 [n,cnt] 형태로 첫번째에는 memo의 인덱스 ( 카드의넘버 ) 가, 두번째 인자로는 해당 쌍을 쓰기 위해 써야하는 코인의 개수를 저장하자. 즉 현재경우

 

able -> [[6,0]] 이 된다. 6번 카드의 쌍 (6,7) 이 완성되었으며 시작부터 완성되어 있으니 소모해야하는 coin은 0개란 의미이다.

 

 

이제 카드를 2개씩 빼며 라운드를 진행하면 된다.

 

1. 카드 넣기 -> 들어온카드를 바탕으로 memo에 1씩 더해준다.

2. able 배열 업데이트 -> 업데이트된 memo가 2가 되었다면 able배열에 넣어준다. 이때 initialMemo와 비교하여 1 혹은 2가 coin소모값이 된다.

배열을 넣은 후에 써야하는 coin기준 내림차순 정렬을 해준다.

3. able 배열이 비어있다면 더이상 라운드 진행이 종료되므로 프로그램을 종료한다.

4. able 배열을 pop하여 이번 턴에 사용할 쌍을 제거하고 , coin을 소모한다.

5. coin이 0보다 작다면 라운드 진행이 종료된 것이므로 프로그램을 종료한다.

6. 지금까지 종료가 안되었다면 다음 라운드를 진행한다.

 

function solution(coin, cards) {
  const n = cards.length;
  const memo = new Array(n / 2 + 1).fill(0);

  //카드를 넣음
  const putCard = (card, ary) => {
    if (card > n / 2) ary[n + 1 - card] += 1;
    else ary[card] += 1;
  };
  //가능배열 초기화
  const updateAble = (card, memo, initial, able) => {
    const num = card > n / 2 ? n + 1 - card : card;
    if (memo[num] === 2) able.push([num, 2 - initialMemo[num]]); //able을 업데이트해줌
    able.sort((a, b) => b[1] - a[1]); // coin 내림차순
  };

  //초기값 설정
  for (let i = 0; i < n / 3; i++) putCard(cards[i], memo);
  let ret = 1;
  const initialMemo = [...memo];
  const able = [];
  for (let i = 1; i < memo.length; i++) {
    if (memo[i] === 2) able.push([i, 0]);
  }

  //라운드 진행
  for (let i = n / 3; i < n; i += 2) {
    putCard(cards[i], memo);
    putCard(cards[i + 1], memo);
    updateAble(cards[i], memo, initialMemo, able);
    updateAble(cards[i + 1], memo, initialMemo, able);

	//able 배열이 비어있는 경우 종료
    if (!able.length) return ret;
    coin -= able.pop()[1];
    //coin 사용이 불가능한 경우 종료
    if (coin < 0) return ret;
    ret++;
  }
  return ret;
}