[leetcode] 565. Array Nesting

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

---

길이가 n인 정수 배열 nums가 주어진다. nums는 [0, n-1] 범위의 겹치지 않는 숫자의 수열이다.

s[k] = {nums[k], nums[nums[k]], nums[nums[nums[k]]] ...} 라 할 때, s[k]의 모든 요소들의 중복이 있지 않아야 한다.

만들 수 있는 s[k]의 최대 길이를 구하라.

---

nums 배열은 유니크한 숫자들로 이루어져있기 때문에 s[k]배열은 사이클이 만들어진다.

예를 들어, nums = {1, 2, 0, 3} 이라면 s[k]가 될 수 있는 배열들은 {1,2,0}, {3}이고 이들은 각각 사이클이 만들어진다.

즉 사이클이 만들어지는 s 배열을 만드는데 이 배열들 중 최장 길이를 구하는 문제이다.

또한 s 배열은 사이클이므로 어느 지점이든 시작지점으로 잡아도 관계가 없다.

 

따라서, nums 배열을 탐색하면서 nums[i] 를 시작점으로 잡고 인덱스를 nums[i]로 이동시키며 길이를 구한다. 이 때, 탐색한 배열의 요소는 -1로 세팅하여 이미 방문했음을 체크한다. 만약 nums[i]가 -1인 경우 사이클이 만들어진 것이므로 탐색을 종료한다. 

 

시간복잡도는 O(n).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/565.%20Array%20Nesting.cpp