[알고리즘] 프로그래머스 131130 혼자 놀기의 달인 자바스크립트

프로그래머스

 

 

 

 

 

 

 

[해설]

1. 1번부터 n번까지의 상자에 들어있는 카드의 값 cards가 주어진다

2. cards[i]에 해당하는 인덱스로 넘어가는데, 이미 방문한 인덱스라면 이동을 종료한다

3. 2번의 횟수를 카운팅한 뒤 정답 배열에 추가한다

4. 정답 배열에서 가장 큰 수와 두 번째로 큰 수를 서로 곱한 값을 출력한다

4-1. 정답 배열의 길이가 2 이하라면 0을 출력한다

 

 

 

 

function solution(cards) {
    const n = cards.length;
    let cardsCountList = [];
    let visited = new Array(n).fill(0);
    let idx = 0;
    let cnt = 0;
    let flag = true;

    while (flag) {
        for (let i=0; i < n; i++) {
            if (visited[idx] === 1) {
                cnt !== 0 && cardsCountList.push(cnt); // 순회를 한 경우(cnt !== 0)만 배열에 저장
                idx = i; // 다음 인덱스로 넘어가기
                cnt = 0;
                continue
            }
            visited[idx] = 1;
            idx = cards[idx] - 1;
            cnt++;
        }
        
        // 하나라도 방문하지 않은 상자가 있다면 반복
        flag = false;
        for (let j=0; j < n; j++) {
            if (visited[j] === 0) {
                flag = true;
                break
            }
        }
    }
    if (cardsCountList.length < 2) {
        return 0
    }
    cardsCountList.sort((a, b) => b - a); // 내림차순 정렬
    return cardsCountList[0] * cardsCountList[1]
}

 

 

시간복잡도는 O(n**2)쯤 나오는 것 같다