백준) 2303 - 숫자게임 JS

📌 문제 링크

https://www.acmicpc.net/problem/2303

---

📌 문제 탐색하기

• N명에게 각각 다섯 장의 카드가 주어졌을 때, 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람을 찾는 프로그램을 작성하시오. 가장 큰 수를 갖는 사람이 두 명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력한다.

시간복잡도

• 플레이어 수 N에 따라 처리 시간이 비례해서 증가하므로 O(n)

알고리즘 선택

• 완전 탐색

---

📌 코드 설계하기

1. 문제를 개행으로 분리하여 `n`과, `input`배열을 가져옵니다.
2. `n`을 숫자로 변환, `input`을 띄어쓰기로 분리하여 숫자로 변환합니다.
3. 카드의 조합을 생성하는 함수 `getCombinations`를 만듭니다.
4. 결과를 담을 `result`변수를 []로 초기화 합니다.
5. 선택할 번호가 1이면 배열을 하나씩 반환해줍니다.
6. `arr`배열을 순회합니다.
7. `rest`변수는 원본 배열에서 `index +1`씩 `slice()`해줍니다.
8. 카드 조합을 생성하는 함수를 반복하며 `combinations` 변수에 할당해줍니다.
9. 기존 값에 `combination`을 결합하여 `acctached `변수에 할당해줍니다.
10. `result` 배열에 `attached`배열 값을 넣어줍니다.
11. 숫자 게임의 최대 값을 찾는 함수를 생성합니다.
12. `maxPlayerValue`와 `winnerIndex` 변수를 초기화합니다.
13. 배열을 순회하면서 3개씩 조합을 찾아 `combinations`에 할당해줍니다.
14. 가장 높은 값을 찾기 위한 `maxValue`를 초기화합니다.
15. `combinations`배열을 순회하면서 일의 자리 값을 찾아 더하고 가장 높은 값을 찾아 `maxValue`에 할당해줍니다.
16. 만약 현재 플레이어의 최대 값이 더 크거나 같다면 결과를 업데이트 해줍니다.
17. 인덱스를 1부터 시작하는 플레이어 번호로 변환합니다.
18. 결과를 출력합니다.

---

📌 정답 코드

const fs = require('fs');
const filePath =
  process.platform === 'linux' ? '/dev/stdin' : __dirname + '/input1.txt';
const [n, ...input] = fs.readFileSync(filePath).toString().trim().split('\n');
const N = Number(n);
const arr = input.map((x: string) => x.split(' ').map(Number));

// 카드의 조합을 생성하는 함수
const getCombinations = (arr: number[], selectNum: number) => {
  const results: number[][] = [];
  if (selectNum === 1) return arr.map((value) => [value]);

  arr.forEach((fixed, index, origin) => {
    const rest = origin.slice(index + 1);
    const combinations = getCombinations(rest, selectNum - 1);
    const attached = combinations.map((combination) => [fixed, ...combination]);
    results.push(...attached);
  });
  return results;
};

// 숫자 게임의 최대 값을 찾는 함수
const findMaxNumber = (cardsList: number[][]) => {
  let maxPlayerValue = 0;
  let winnerIndex = 0;

  cardsList.forEach((cards, playerIndex) => {
    const combinations = getCombinations(cards, 3);
    let maxValue = 0;

    combinations.forEach((comb) => {
      const sumLastDigit =
        comb.reduce((acc: number, cur: number) => acc + cur, 0) % 10;
      maxValue = Math.max(maxValue, sumLastDigit);
    });

    // 현재 플레이어의 최대 값이 더 크거나 같다면 결과 업데이트
    if (maxValue >= maxPlayerValue) {
      maxPlayerValue = maxValue;
      // 인덱스를 1부터 시작하는 플레이어 번호로 변환
      winnerIndex = playerIndex + 1;
    }
  });

  return winnerIndex;
};

console.log(findMaxNumber(arr));