[프로그래머스 LV2] 혼자 놀기의 달인

문제

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

아이디어

전체 카드를 순회하면서, 모든 상자 그룹을 구한다.
각 상자 그룹의 길이를 가지고 내림차순으로 정렬한다.
만약 상자 그룹이 2개보다 적다면 점수는 0 이고, 그렇지 않다면 첫 번째 상자 그룹의 길이 * 두 번째 상자 그룹의 길이 이다.

소스코드

// firstIdx 번째 요소부터 시작하여 카드 상자 그룹을 구하는 함수
function findBoxGroup(firstIdx, cards, visited) {
  const result = [];

  if (firstIdx > 0) {
    let next = cards[firstIdx];

    while (!visited[next]) {
      result.push(next);
      visited[next] = 1;
      next = cards[next];
    }
  }

  return result;
}

// 모든 카드 상자 그룹을 구하는 함수
function findAllBoxGroup(cards) {
  const queue = [];
  const visited = Array.from({ length: cards.length }, () => 0);

  for (let i = 1; i < cards.length; i++) {
    if (visited[i]) continue;

    const box = findBoxGroup(i, cards, visited).sort((a, b) => a - b);
    queue.push(box);
  }

  return queue;
}

function solution(cards) {
  cards.unshift(0);

  const groups = findAllBoxGroup(cards).sort((a, b) => b.length - a.length);

  if (groups.length < 2) return 0;
  else return groups[0].length * groups[1].length;
}