[JS] Leetcode 565. Array Nesting

문제 링크 : https://leetcode.com/problems/array-nesting/

Solution

Frist Solution

// leetcode 565. Array Nesting

// Example
// Input: nums = [5,4,0,3,1,6,2]
// Output: 4
// Explanation: 
// nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
// One of the longest sets s[k]:
// s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

'use strict'

/**
 * @param {number[]} nums
 * @return {number}
 */
const arrayNesting = function(nums) {
    let answer = 0;  // 최종 정답
    let set = new Set();
    let count;  // 순회 깊이를 나타내는 변수

    // 해당 idx에 해당하는 값 탐색해보는 함수
    const dfs = (k) => {
        if(set.has(k)){
            return  
        } else {
            set.add(k);
            count += 1;
            dfs(nums[k]);
            return;
        }
    }

    // idx 별로 
    nums.forEach((val, idx) => {
        count = 0;
        dfs(idx);
        answer = (count >= answer) ? count : answer;
    })

    return answer;
};

// execute
const nums = [5,4,0,3,1,6,2];
console.log(arrayNesting(nums));

코드 설명 : k -> nums[k] -> nums[nums[k]] 이런 순으로 탐색하기 때문에 아무래도 탐색했던 것들을 다시 탐색하는 경우가 발생할 수 있다.

예시: [5,4,0,3,1,6,2]

s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}
즉, nums[2]를 탐색했을 시 다시 nums[0]을 탐색하기 때문에 탐색했던 것을 무한정으로 순회할 수 있다.

그리고 똑같은 숫자를 사용할 수 없기에 순회를 함에 있어서 교집합이 발생할 수 없다. 위의 코드를 예시로 보자면
s[0]: 5 -> 6 -> 2 -> 0 을 무한정 순회
s[1]: 1 -> 4를 무한정 순회
s[3]: 자기 자신을 계속 가리킴

이렇게 겹치는 부분이 없게 된다. 따라서 idx 부분을 하나씩 탐색을 하면서 해당 탐색하려는 idx 부분이 방문을 했다면 다음 idx를 탐색하는 방법을 사용하게 되면 시간 복잡도를 줄일 수 있다.

    // 해당 idx에 해당하는 값 탐색해보는 함수
    const dfs = (k) => {
        if(set.has(k)){
            return  
        } else {
            set.add(k);
            count += 1;
            dfs(nums[k]);
            return;
        }
    }

Second Solution

• 첫번째 solution에서 재귀함수를 사용했을 때 시간복잡도가 상당히 느린 것을 볼 수 있었다. 따라서 이번에는 bfs를 사용해 메모리 사용량과 시간복잡도를 줄여볼 생각이다.

// leetcode 565. Array Nesting

// Example
// Input: nums = [5,4,0,3,1,6,2]
// Output: 4
// Explanation: 
// nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2.
// One of the longest sets s[k]:
// s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

'use strict'

/**
 * @param {number[]} nums
 * @return {number}
 */
const arrayNesting = function(nums) {
    let answer = 0;
    let depth;
    // visited = [false] * len(nums);
    // new Array(nums.length).fill(false) => 이건 시간 복잡도가 오래 걸림
    let visited;
    (visited = []).length = nums.length;
    visited.fill(false);

    const bfs = (k) => {
        while (!visited[k]){
            depth += 1;
            visited[k] = true;
            k = nums[k];
        }
    }
    
    nums.forEach((val, idx) => {
        depth = 0;
        bfs(idx);
        answer = (depth >= answer) ? depth : answer; 
    })

    return answer;
};

코드 설명: visited 라는 배열을 통해 각 idx 별로 방문여부를 판단하였다.
추가적으로

 // new Array(nums.length).fill(false) => 이건 시간 복잡도가 오래 걸림
    let visited;
    (visited = []).length = nums.length;
    visited.fill(false);

위의 구문을 사용하여 시간복잡도를 줄여보려고 했다.
-> new Array사용 시 객체 생성하는 데 시간이 좀 더 걸린다고 한다.

어려웠던 점

문제는 전반적으로 어렵지 않았지만 기존의 파이썬으로 알고리즘을 풀어 알고리즘 풀이 형식에 익숙해져 있었다. 그래서 파이썬 특유의 배열의 최대값을 구하는 함수 max()함수 + 배열 * n 이런 것에 많이 익숙해져서 구글링을 통해 이를 해결하였다.

결론 : 자바스크립트 사용에 익숙해지자!!