[LeetCode] Array Nesting - 21.09.01

📄 문제

nums라는 길이 n의 int 배열이 있고, [0, n-1] 범위의 원소가 하나씩 무작위로 배열되어 있다.
ex) n = 6, [1, 3, 4, 5, 0, 2]
이 때, s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]], ... }라는 배열을 만들 수 있는데, 최대 길이를 갖는 s 배열을 찾아서 그 길이를 return하는 것이 본 문제의 목표이다.
문제 링크

🔍 코드

class Solution {
    public int arrayNesting(int[] nums) {
        int len = nums.length;
        int answer = 0;
        
        for (int i = 0; i < len; i++) {
            if (nums[i] == i) {
                answer = Math.max(answer, 1);
                continue;
            }
            
            int iterLen = 0;
            if (nums[i] != len) {
                int iter = nums[i];
                while (true) {
                    int tmp = iter;
                    iter = nums[iter];
                    nums[tmp] = len;
                    if (iter == len) {
                        break;
                    }
                    iterLen++;
                }   
            }
            answer = Math.max(answer, iterLen);
            if (answer > Math.ceil(len / 2.0)) {
                return answer;
            }
        }
        return answer;
    }
}

✅ 풀이

1. 우선, 원소의 위치와 원소의 값이 같으면 s의 길이는 1이 된다.
2. 1번 조건에 맞지 않는다면, 규칙에 따라 배열을 순회하게 될 것이고, 이 때 s의 길이가 nums의 길이의 반 정도보다 클 경우는 최종 정답이 된다.
3. 2번의 조건에 맞지 않는다면, s의 길이는 iterLen에 저장되며, iterLen과 answer 중 큰 값이 answer에 업데이트된다.
4. 방문한 노드는 nums의 길이로 업데이트한다.