[프로그래머스 Level 2] 혼자 놀기의 달인 - JavaScript

🔗 문제 링크

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

프로그래머스

✏️ 풀이

function solution(cards) {
    const openBoxes = (start, opened) => {
        let box = start;
        let count = 0;
        while (!opened[box]) {
            opened[box] = true;
            box = cards[box] - 1;
            count++;
        }
        return count;
    };
    
    let maxScore = 0;
    
    for (let i = 0; i < cards.length; i++) {
        const opened = Array(cards.length).fill(false);
        const group1 = openBoxes(i, opened);
        for (let j = 0; j < cards.length; j++) {
            if (opened[j]) {
                continue;
            }
            const group2 = openBoxes(j, opened);
            maxScore = Math.max(maxScore, group1 * group2);
        }
    }
    
    return maxScore;
}

각 상자가 열려 있는지 여부를 opened 배열에 저장하고, 상자를 열 수 있을 때까지 여는 행위를 1회 하는 것을 openBoxes라는 함수로 정의하였다. openBoxes에서는 열기 시작한 상자부터 열 수 있는 모든 상자를 다 열고, 연 상자의 개수를 반화한다.

 

for문으로 cards를 순회하면서 각 상자(카드)부터 열기 시작하는 경우를 모두 구하도록 하였다. 순회를 할 때마다 opened를 새로 갱신하고 openBoxes를 1회 실행하여 1번 상자 그룹(group1)의 개수를 구한다. 그리고 나서 다시 cards를 또 순회하면서 아직 열지 않은 상자들 중에서 다시 한 번 openBoxes를 1회 실행하여 2번 상자 그룹(group2)의 개수를 구한다. 그리고 나서 group1과 group2의 곱으로 maxScore를 갱신한다. 만약 1번 상자 그룹에서 모든 상자를 다 연 경우에는 2번 상자 그룹이 없는데, 어차피 그런 경우에는 group2가 무조건 0이 되므로 1번 상자 그룹에서 모든 상자를 여는 경우에 점수가 0점이 되는 규칙을 자연스럽게 만족하게 된다.