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

문제

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

접근 방법

카드 번호를 따라 상자를 열면 하나의 순환을 이루는 상자 그룹을 찾을 수 있다. 카드 번호는 1부터 시작하지만 배열 인덱스는 0부터 시작하므로, 다음 인덱스는 cards[current] - 1이다. 카드에 적힌 번호 자체에서 1을 빼는 규칙이 있는 것은 아니다.

카드 번호가 중복되지 않는 순열이므로 서로 다른 그룹은 겹치지 않는다. 아직 열지 않은 상자에서 출발해 이미 열린 상자를 만날 때까지 방문하고, 그룹의 크기만 기록한다. 재귀 대신 반복문을 사용하면 호출 스택에 의존하지 않는다.

모든 그룹을 찾은 뒤 가장 큰 두 그룹의 크기를 곱한다. 어느 상자에서 시작해도 해당 그룹의 크기는 같으므로, 이 두 그룹을 선택해야 최대 점수를 얻는다. 그룹이 하나뿐이면 두 번째 그룹을 선택할 수 없어 점수는 0이다.

코드

function solution(cards) {
  const opened = Array(cards.length).fill(false)
  const sizes = []

  for (let start = 0; start < cards.length; start++) {
    if (opened[start]) continue

    let current = start
    let size = 0
    while (!opened[current]) {
      opened[current] = true
      size += 1
      current = cards[current] - 1
    }
    sizes.push(size)
  }

  sizes.sort((a, b) => b - a)
  return sizes.length < 2 ? 0 : sizes[0] * sizes[1]
}

복잡도와 경계 조건

상자 수가 n, 그룹 수가 g이면 탐색은 O(n), 그룹 정렬은 O(g log g)이다. 추가 공간은 O(n)이다.

하나의 순환으로 이루어진 경우와 모든 상자가 자기 자신을 가리키는 경우에도 각각 0과 1을 반환한다.