[Leetcode 287] - Find the Duplicate Number w/ Python

문제

 

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive. 

There is only one repeated number in nums, return this repeated number. 

You must solve the problem without modifying the array nums and uses only constant extra space.

 

 

주어진 리스트의 길이가 n + 1이다. 이 리스트에서 반복되는 숫자는 딱 한개인데 이를 리턴해야된다.

추가로 리스트에 있는 숫자를 수정할 수도 없고 O(1)에 비례되는 추가 메모리만 사용 가능하다.

 

 

https://leetcode.com/problems/find-the-duplicate-number/description/

 

 

---

 

예시

 

 

Example 1:

Input: nums = [1,3,4,2,2]
Output: 2

 

Example 2:

Input: nums = [3,1,3,4,2]
Output: 3

 

Example 3:

Input: nums = [3,3,3,3,3]
Output: 3

 

---

 

풀이

 

문제를 처음 봤을때는 굉장히 간단해 보였다.

" 그냥 해시맵 써서 반복되는거 찾으면 끝...?"

 

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        numMap = set()
        
        for num in nums:
        	if num in numMap:
                return num
            else:
                numMap.add(num)

 

풀리긴 풀린다

 

근데 문제에 나온대로 메모리 사용을 최소화 해야되기 때문에

풀이 방식이 틀렸다는것을 알게 되었다

 

---

 

 

이에 플로이드의 토끼와 거북이를 써야된다는것은 알았는데

Cycle Detection을 도대체 어떻게 해결해야될지 감이 안잡혀서 Neetcode를 참고 했다

 

글쓴이도 역시 이 문제는 미리 알고 있지 않으면 절대 통과 못할 정도의 수준이라며

강한 비판하는것을 듣고 나름 안심...?을 하게 되었다.

 

문제의 핵심은 수학적으로 풀이를 해봤을때 플로이드 알고리즘을 쓰면

루프 시작점을 찾기 전의 리스트 길이와 루프 내부에서 시작점으로 가는

길이가 언제나 같다는것이다

 

사진을 통해 설명하는게 편할것 같아서 한번 만들어 왔다.

1. 제일 좌측이 시작점

2. 초록색이 루프가 시작하는 노드/자리

3. 빨간색이 시작점에서 초록색까지 도달하기 위한 거리

- 즉 시작점에서 초록색까지 도달하려고 하는 거리 1이라면 다른 포인터 역시 1이 된다

- 2라면 반대로도 2가 무조건 된다

예시 1

예시 2

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0
        
        # 첫번째 루프는 둘이 만나는 지점을 찾기 위해
        # 무조건 루프 내부에서 루프 시작점 - 리스트 시작점 = 빨간색 위치
        while True: # 첫번째 루프는 둘이 만나는 지점을 찾기 위해
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        
        slow2 = 0 # 포인터 한개는 다시 시작점으로
        # 이제 두개의 포인터가 만날때 결과를 리턴하면 된다
        while True:
            slow = nums[slow]
            slow2 = nums[slow2]
            if slow == slow2:
                break
        return slow

메모리 효율 미쳤구

 

솔직히 이 문제를 모르는 상태에서 면접에서 주어진다면 90% 떨어질것 같은 느낌이 든다

이해하고 나서 설명하기도 힘든데... 분명 쉬워 보이는데...

플로이드도 이 문제를 처음 보면 갸우뚱할것 같은 느낌