프로그래머스 - 혼자 놀기의 달인

Link

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

접근 방법

이 문제는 알고리즘을 딱히 활용하지 않아도 되는 단순 구현 문제이다.

지문을 읽으면서 요구사항을 정리해 보면 다음과 같다.

• 최소 2개, 최대 100개의 상자에 카드가 들어있다.
• 카드는 무작위로 상자에 들어가 있고, 적힌 번호는 상자의 총 개수 이하의 자연수이다.
• 임의의 상자를 열어서 카드 번호를 확인하면, 그 카드 번호는 다음에 열어야 할 상자의 번호 - 1가 된다.
• 다음에 열어야 할 상자가 이미 열려있다면, 상자를 열어가면서 확인한 카드는 같은 그룹이 된다.
• 게임의 점수는 두 그룹의 카드 개수를 곱한 것이다. 단, 문제에서 요구한 것은 "최대 점수"이다.
• 만약 그룹이 한 개 뿐이라면, 게임의 점수는 0이다.

정리한 요구사항 중 구현이 필요한 것들을 단순히 구현해나가면 풀리는 문제이다.

Implementation

• 임의의 상자를 열어서 카드 번호를 확인하면, 그 카드 번호는 다음에 열어야 할 상자의 번호 - 1가 된다.
• 다음에 열어야 할 상자가 이미 열려있다면, 상자를 열어가면서 확인한 카드는 같은 그룹이 된다.

let opened = Array(cards.length).fill(false);
let groups = [];
const opening = (group, boxNum, cards) => {
  if (opened[boxNum] === true) {
    if (group.length) {
      groups.push(group);
    }
    return;
  } else {
    opened[boxNum] = true;
    group.push(cards[boxNum]);
    opening(group, cards[boxNum] - 1, cards);
  }
};
for (let idx = 0; idx < cards.length; idx++) {
  opening([], idx, cards);
}

• 게임의 점수는 두 그룹의 카드 개수를 곱한 것이다. 단, 문제에서 요구한 것은 "최대 점수"이다.

const score = groups.map((group) => {
  return group.length;
});

const sortedScore = score.sort((a, b) => b - a);

• 만약 그룹이 한 개 뿐이라면, 게임의 점수는 0이다.

if (!score[1]) {
  return 0;
} else {
  return sortedScore[0] * sortedScore[1];
}

Code

function solution(cards) {
  let opened = Array(cards.length).fill(false);
  let groups = [];
  const opening = (group, boxNum, cards) => {
    if (opened[boxNum] === true) {
      if (group.length) {
        groups.push(group);
      }
      return;
    } else {
      opened[boxNum] = true;
      group.push(cards[boxNum]);
      opening(group, cards[boxNum] - 1, cards);
    }
  };
  for (let idx = 0; idx < cards.length; idx++) {
    opening([], idx, cards);
  }
  const score = groups.map((group) => {
    return group.length;
  });

  const sortedScore = score.sort((a, b) => b - a);

  if (!score[1]) {
    return 0;
  } else {
    return sortedScore[0] * sortedScore[1];
  }
}