[프로그래머스] 혼자 놀기의 달인 풀이 / JavaScript

프로그래머스

작성 코드 (1차 시도 / 통과)

function solution(cards) {
    const visited = Array(cards.length + 1).fill(0)
    visited[0] = 1
    let [group, result] = [[], []]
    let idx = cards[0]
    while (1) {
        if (visited.indexOf(0) === -1) { // 더이상 방문할 원소가 없는 경우
            result.push(group)
            break
        } else if (!visited[idx]) { // 방문하지 않은 경우 방문 처리
            visited[idx] = 1
            group.push(idx)
            idx = cards[idx - 1]
        } else { // 이미 방문한 경우 == 그룹 완성
            idx = visited.indexOf(0)
            result.push(group)
            group = []
        }
    }
    result.sort((a, b) => b.length - a.length) // 배열 길이 순으로 정렬
    return result.length !== 1 ? result[0].length * result[1].length : 0 // 가장 높은 길이의 두 그룹 곱수 반환
}

구현 로직

cards의 배열을 바꾸면 안되고 주어진 순서대로 로직을 짜야합니다. 그룹1이 1, 4, 7, 8이 모이는 이유는 시작 idx를 cards의 첫번째 원소로 잡았을 때 그룹1에 8넣고, 8번째 인덱스인 4넣고, 4번째 인덱스인 7넣고, 7번째 인덱스인 1넣고, 1번째 인덱스는 다시 8이므로 그룹1이 이렇게 완성되고 다음 그룹도 마찬가지 형태로 생성되는 원리입니다.

 

그룹에 들어갈 때마다 방문 처리(visited)만 해주면 시작 idx를 cards의 어떤 원소로 해도 동일한 결과의 그룹들이 생성됩니다.

생성되는 그룹은 result에 넣어두고 배열 길이순으로 정렬해서 가장 긴 길이의 그룹1과 2의 길이를 곱한 값을 리턴하면 됩니다.

 

1. 현재 인덱스에 해당하는 원소가 방문되지 않은 경우 방문 처리 후 group에 푸시. 인덱스는 원소로 변경.

2. 이미 방문 한 경우 그룹이 완성되고 결과 배열에 푸시

3. 모든 원소를 방문하였다면 현재 그룹에 들어있는 값을 결과 배열에 넣고 종료

4. 결과 배열을 정렬하여 가장 긴 길이의 두 그룹의 길이의 곱을 반환