[LeetCode] 565. Array Nesting

- Problem

565. Array Nesting

확신의 dfs 문제이다.
주어진 규칙에 맞는 가장 긴 배열의 길이를 반환해야 한다.

key point는 주어진 규칙에 따라 nums를 순회하면, 일종의 cycle이 형성된다는 것이다.

cycle이 형성된다는 것을 주의하여 해결하면 의외로 간단하다.

- 내 풀이

class Solution:
    def arrayNesting(self, nums: List[int]) -> int:
        answer = 0
        
        for num in nums:
            cnt = 0
            while nums[num] != -1:
                nums[num], num = -1, nums[num]
                cnt += 1
            answer = max(answer, cnt)
        
        return answer

처음에는 방문 기록을 담는 set 자료형을 써볼까 했지만, 주어진 배열 nums의 원소 값을 -1로 바꿔주고, 이를 확인한다면 굳이 추가적으로 메모리를 소모하지 않아도 된다.

- 결과

100%?