[Misc][Medium] 287. Find the Duplicate Number

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

 

 

Q. 주어진 정수배열 nums는 1부터 배열의 길이까지의 값을 가진다. 이때 하나의 값이 더 있고, 이 값이 기존 값들 중 하나와 중복일 때, 이 중복 값을 찾아라. 

  이때, 기존 배열을 수정하지 말고, 추가 메모리도 사용하지 말아라. 

 

 

Solution. 

 우선 제한을 생각하지 말아 본다. 

 

 2중 루프들 돌며 중복 값을 찾는다. -> O(N x N)으로 TL 오류. 

 추가 버퍼를 가지고 flag checking 한다. -> In Place memory limitation.

 정렬하고 중복찾기 -> 기존 배열 수정 금지 오류. 

 

 따라서 다른 접근이 필요하다. 

 

 각 배열을 link list node라고 생각한다. 또한 해당 위치값을 다음 노드의 포인팅 값이라고 생각해 본다. 

 

 그러면 중복이 있으므로, 같은 노드를 포인팅 하는 지점이 있다는 것이다. 

 이것은 즉, list의 cycle이 된다. 

 

 또한 이 중복 값은 다른 노드들이 가지고 있는 같은 다음 노드값이 되므로, 즉 cycle 시작점이 된다. 

 

 따라서 linked list의 cycle을 찾는 로직을 대입해서 코드를 만들어 본다. 

 

 

public int FindDuplicate(int[] nums) 
{
    int fast = 0;
    int slow = 0;
    bool bLoop = false;
    while(fast<nums.Length && nums[fast]<nums.Length)
    {
        slow = nums[slow];
        fast = nums[ nums[fast] ];
        if(slow == fast)
        {
            bLoop = true;
            break;
        }
    }
    if(!bLoop)  return -1;

    fast = 0;
    while(fast<nums.Length)
    {
        if(slow == fast)
            return slow;

        slow = nums[slow];
        fast = nums[fast];
    }
    return -1;
}

 

적절한 결과를 얻었다.

 

 

이런 류의 문제가 참 많다. 

즉, 풀이의 실마리를 찾으면 쉽게 풀리지만, 

그렇지 못하면 기존의 접근법들로는 쉽게 풀리지 않게 된다. 

 

따라서 훈련이 중요한 이유다.