287. Find the Duplicate Number

• 처음 봤을때 sorting 이나 set을 쓰면 되겠지 했지만… array를 수정할 수 없고, constant storage complexity O(1), linear time complexity O(n) 제약 조건이 있어서 사용할 수 없어서 어려웠던 문제이다.

• Floyd's Tortoise and Hare 알고리즘을 사용해야 한다.
• Linked list에서 cycle이 존재할 때 cycle의 시작점을 찾을 수 있는 알고리즘이다.
• 그래프의 모양은 풍선 (cycle) 끝에 선 (index 0 시작점)이 붙어있는 모양이 된다.

• 문제는 cycle의 시작점이 어째서 중복된 값일 수 있는가 하는 점이다.
• 이는 array에 중복된 값이 있을 경우 그래프에서 중복된 값에 대한 노드만이 유일하게 들어오는 연결이 2개 이상이기 때문이다.
• 나머지 값에 해당하는 노드는 들어오는 연결이 하나이므로 index 0 시작점 → cycle의 시작점 또는 cycle 내부에 위치하게 된다.
• 물론 일부 노드는 index 0 시작점 선에서 닿는 cycle을 형성하는데에서 제외될 수 있다.
• 아래 그림은 이해를 돕기 위해서 index 0을 포함시켰지만 알고리즘에서는 index 0이 가리키는 지점 부터 시작한다.
• 물론 index 0으로 시작해도 결과는 같다.

• 알고리즘이 동작하는 원리는 다음과 같다.

조건 index 0 시작점 → cycle의 시작점까지의 길이를 m, cycle의 길이를 n이라고 하자. 둘이 만나기까지 거북이가 돈 바퀴 수를 a, 토끼가 돈 바퀴 수를 b라고 하자. cycle의 시작점부터 토끼와 거북이가 cycle에서 만난 지점까지의 거리를 k라고 하자.

풀이 첫번째 단계에서 둘이 만나기까지 거북이가 이동한 거리는 m + a * n + k, 토끼가 이동한 거리는 m + b * n + k가 된다. 토끼가 이동한 거리는 거북이가 이동한 거리의 2배가 되므로 2 * (m + a * n + k) = m + b * n + k 가 된다. 정리하면 m = (b - 2a) * n - k 가 된다. ——— 이제 두번째 단계에서는 거북이는 그래프의 시작 위치(index 0)로 이동한 상태에서, 토끼는 둘이 만난 위치 (cycle의 시작점 기준으로 k) 에서 둘다 한칸씩 움직이게 된다. 거북이가 그래프의 시작 위치에서 m 만큼 이동하면 cycle의 시작점 0 에 도달한다. 한편 토끼는 cycle의 시작점을 기준으로 (k + m) % n 위치에 도달한다. (k + m) % n = (k + (b - 2a) * n - k) % n = ((b - 2a) * n) % n = 0 즉, 토끼도 cycle의 시작점에 도달하게 된다.

• 시간 복잡도는 O(n) 인데 이는 풀이에서 보이듯이 둘의 이동 거리 (array 조회 연산의 수)가 n에 비례하기 때문이다.

• 참고: https://en.wikipedia.org/wiki/Cycle_detection#Floyd's_tortoise_and_hare

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int start = nums[0];
        int t = nums[start];
        int h = nums[t];
        while (t != h) {
            t = nums[t];
            h = nums[nums[h]];
        }
        t = start;
        while (t != h) {
            t = nums[t];
            h = nums[h];
        }
        return t;
    }
};