[Leetcode] 287. Find the Duplicate Number

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

---

[1, n] 범위의 정수들로 이루어진 n+1 크기의 배열 nums가 주어진다. 이 배열엔 중복된 숫자가 하나만 존재파는데 중복된 숫자를 구해라.

단, nums 배열은 수정하지 않아야 하고 상수 크기의 추가 공간만 사용해야 한다.

---

Floyd's cycle detection 으로 풀었다.

nums 배열은 [1, n] 범위의 정수들로 이루어지고 중복된 숫자는 하나 밖에 없다는 조건을 이용해보자.

index -> nums[index] 로 방향이 있는 간선을 연결하면 중복된 숫자가 하나가 존재하므로 순환이 발생하게 된다.

이 순환의 시작점이 중복된 숫자가 될 것이다. 순환의 시작점이 되는 지점(let, v)은 진입차수(in-degree)가 2개가 될 것이고 이는 u->v를 만족하는 u가 2개가 됨을 의미하는데. 즉, u -> nums[u] (= v). 식에서의 u, 즉 index가 2개존재함을 의미함과 같다. 따라서 동일한 정수 v를 가지는 2개의 index가 존재하는 v가 정답이 된다.

 

여기에서 Floyd's cycle detection을 구하는 플로이드의 거북이와 토끼 방법을 사용하여 v를 구할 수 있다.

 

알고리즘 이론 카테고리가 아니니까 간단히만 말하자면

while(slow != fast) {
	slow = nums[slow];
	fast = nums[nums[fast]];
}

위 로직을 돌려서 slow 와 fast가 같아지는 지점을 한 번 찾고 slow를 다시 초기값으로 갱신 

while(slow != fast) {
	slow = nums[slow];
	fast = nums[fast];
}

이번엔 위 로직을 돌려서 slow와 fast가 동일해졌을 때의, slow, fast 가 순환의 시작점이 되는 지점, v가 된다.

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/287.%20Find%20the%20Duplicate%20Number.cpp

---

참고 : https://leetcode.com/problems/find-the-duplicate-number/discuss/1892999/Simple-easy-solution-c%2B%2B

so genius.

이진탐색 어느정도 됐으니까 이제 이거 좀 풀어봐야지