[프로그래머스 lev2/JS] 혼자 놀기의 달인

문제 출처

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

나의 풀이

1차시도 (70/100)

첫번째 상자 그룹에서 모든 상자를 여는 경우에서 문제가 생기는 것 같다.

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

  const selectNum = (arr, idx, cnt) => {
    if(arr[idx] === 0) return cnt
    let newIdx = arr[idx]
    arr[idx] = 0
    return selectNum(arr, newIdx, cnt+1)
  }
  
  let set = new Set()
  for(let i=1; i<cards.length; i++){
    let copy = [...cards]
    let cases = selectNum(copy, i, 0)
    if(cases === cards.length) {
      set.add(0)
      continue
    }
    set.add(cases)
  }

  let answer = Array.from(set).sort((a,b) => b-a)
  return answer[0] * answer[1]
}

console.log(solution([8, 6, 3, 7, 2, 5, 1, 4])) // 12

2차시도 (통과)

어떤 카드에서 시작하느냐에 따라 경우의 수가 나뉜다.
그러므로 for문을 사용해서 경우의 수를 따진다.

각 index마다 재귀를 통해 첫번째 상자 그룹을 찾는다.
그리고 나서 두번째 상자 그룹을 찾은 뒤, 최댓값을 계속해서 갱신해준다.

재귀는 간단하게 value에서 index로 연결하면 된다.

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

  const selectNum = (arr, idx, cnt) => {
    if(arr[idx] === 0) return cnt
    let newIdx = arr[idx]
    arr[idx] = 0
    return selectNum(arr, newIdx, cnt+1)
  }
  
  let answer = 0
  for(let i=1; i<cards.length; i++){
    let copy = [...cards]
    let first = selectNum(copy, i, 0)
    let second = 0

    for(let j=1; j<copy.length; j++) {
      if(copy[j] !== 0) second = Math.max(second, selectNum(copy, j, 0))
    }
    answer = Math.max(answer, first*second)
  }
  return answer
}

다른 풀이

const solution = (cards) => {
  const answer = [];
  cards.forEach((v, i) => {
    let idx = i;
    let count = 0;
    while (true) {
      if (cards[idx]) {
        const temp = cards[idx];
        cards[idx] = 0;
        idx = temp - 1;
        count++;
      } else {
        answer.push(count);
        break;
      }
    }
  });
  const sortAnswer = answer.filter((v) => v != 0).sort((a, b) => b - a);

  return sortAnswer.length > 1 ? sortAnswer[0] * sortAnswer[1] : 0;
};