565. Array Nesting (배열 중첩)

길이 n의 정수 배열 번호가 주어집니다. 여기서 nums는 [0, n - 1] 범위에 있는 숫자의 순열입니다.

다음 규칙에 따라 s[k] = {nums[k], nums[nums[k]], nums[nums[k]], ...} 집합을 구성해야 합니다:

• s[k]의 첫 번째 요소는 인덱스 = k의 요소 번호[k] 선택으로 시작합니다.
• s[k]의 다음 요소는 nums[k], nums[k], nums[k] 등이어야 합니다.
• s[k]에 중복 요소가 발생하기 직전에 추가를 중지합니다.

s[k] 집합의 가장 긴 길이를 반환합니다.

 

예시 1:

입력: nums = [5,4,0,3,1,6,2]
출력: 4
설명:
nums[0] = 5, nums[1] = 4, nums[2] = 0, nums[3] = 3, nums[4] = 1, nums[5] = 6, nums[6] = 2입니다.
가장 긴 집합 중 하나[k]:
s[0] = {nums[0], nums[5], nums[6], nums[2]} = {5, 6, 2, 0}

 

예시 2:

입력: nums = [0,1,2]
출력: 1

 

조건:

• 1 <= nums.length <= 10^5
• 0 <= nums[i] < nums.length
• 모든 숫자 값은 고유합니다.

 

오답:

public class Solution {
    public int ArrayNesting(int[] nums) {
        int result = 0;
        
        for (int i = 0; i < nums.Length; i++)
        {
            int count = 0;
            int index = i;
            List<int> check = new List<int>();
            check.Add(index);
            
            while (check.Count == check.Distinct().Count())
            {
                index = nums[index];
                check.Add(index);
                count += 1;
            }
            
            if (result < count)
            {
                result = count;
            }
        }
        
        return result;
    }
}

 

정답:

public class Solution {
    bool[] isCheck;
    int result = 0;

    public int ArrayNesting(int[] nums) {
        isCheck = new bool[nums.Length];
        for(int i = 0;i<nums.Length;i++)
        {
            Dfs(nums, i, 1);
        }

        return result;
    }

    public void Dfs(int[] nums, int index, int count)
    {
        if(isCheck[index])
        {
            return;
        }

        isCheck[index] = true;

        result = Math.Max(result, count);

        Dfs(nums, nums[index], count+1);
    }
}

해설: 오답은 각 index의 출발점마다 셀 수 있는 count 값을 체크하여 가장 높은 수를 가지고 있는 수를 반환해주어서 풀어주었지만 역시나 Time Limit가 걸려서 다시 해결하였습니다.

그 다음으로 해결한 방식은 깊이 우선 탐색을 이용하였습니다.

isCheck에서 해당 nums index가 사용하였는지 체크하였습니다.

그 외의 기능은 오답에서의 기능과 크게 차이가 없습니다.