[LeetCode 해석 및 풀이] 287. Find the Duplicate Number

LeetCode 문제 해석 및 풀이 방법

 

문제 287. Find the Duplicate Number(반복되는 수 찾기)

바로가기

 

문제 설명

영문

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.

 

Follow up:

• How can we prove that at least one duplicate number must exist in nums
• Can you solve the problem in linear runtime complexity?

 

한글

범위 [1,n]의 정수 n+1개가 들어있는 정수 배열 nums가 주어집니다

 

nums안에는 오직 한 종류의 반복되는 숫자가 있으며, 이 반복되는 숫자를 반환하십시요.

 

반드시 배열 nums를 바꾸지 않고 오직 정해진 추가 공간을 써야 합니다.

 

추가:

• 어떻게 중복되는 숫자가 적어도 한개 있음을 증명할 수 있습니까?
• 선형 시간복잡도로 해당 문제를 풀 수 있나요?

 

제한조건

• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

 

입출력 예

입력	출력
nums = [1,3,4,2,2]	2
nums = [3,1,3,4,2]	3
nums = [3,3,3,3,3]	3

 

 

해답 및 해설

우선 비둘기집의 원리에 의해 n+1개의 정수가 있는 배열에서 1부터 n까지의 수 밖에 없다면 적어도 한 수는 중복되게 있을 수 밖에 없다.

 

파이썬 (Python)

브루트 포스로 찾기

모든 수를 각각의 다른 수와 비교한다. O(n^2)의 시간 복잡도가 걸리므로 그리 좋은 방법은 아니다.

 

비트 마스킹을 이용

 우선 해쉬로 중복을 확인하거나 DAT를 이용하여 숫자의 빈도를 세는 방식은 O(1)의 공간복잡도가 아니므로 문제의 조건도 만족하지 않는다. 또한 배열의 숫자의 부호를 바꾼다거나 하는 식으로 중복되는 숫자가 있는지 원래 배열에 표기해주는 방식은 기존 배열을 바꾸므로 역시 조건을 만족하지 않는다.

 

 그래서 태그에 나온대로 비트 마스킹 (Bit Manipulation)을 이용해 특정 숫자가 나왔는지 아닌지 체크를 할 것이다.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        mask = 0

        for num in nums:
            check = 1 << (num-1)

            if mask & check:
                return num

            mask += check
        
        return 'error'

 

nums를 반복문 돌려 num 일 때 이진법에서 mask 숫자를 봤을 때 num-1자리의 숫자가 무엇인지 확인한다. 이전에 표기해두어 숫자가 1이라면 해당 숫자가 중복된 숫자이므로 해당 숫자를 반환하고, 아니라면 해당 자릿수를 1로 변경한다.

 

해당 방법은 check하는 숫자를 뽑기 위해 shift하는 과정 때문에 시간 복잡도가 O(n^2)이 걸리는 듯 하다. 또한 해당 방법이 엄밀하게 O(1)의 공간복잡도라고 말해야 되는지도 의문이다.

 

이진 탐색을 이용

1부터 n 사이의 어떤 정수 num이 있을 때, nums에서 해당 정수보다 작은 수의 갯수를 샌다고 해보자. 만약 그 갯수가 num보다 크다면 중복되는 정수는 num보다 작은 수 일것이다.

 

이 원리를 이용하여 1부터 n 사이의 범위에서 이진 탐색을 하여 중복되는 수를 찾아내도록 한다.

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        low, high = 1, len(nums) - 1
        
        while low < high:
            mid = (low + high) // 2
            count = 0
            
            for num in nums:
                if num <= mid:
                    count += 1

            if count > mid:
                high = mid
            else:
                low = mid + 1
                
        return low

 범위를 1부터 n까지 잡은 후, 중간수 mid를 잡는다. 그 후 배열 nums에 mid 이하의 수가 몇개 있는지 센다. 만약 그 값이 mid보다 크다면 범위의 최댓값을 mid로 바꾼다. 만약 아니라면 범위의 최솟값을 mid +1로 바꾼다. 이 과정을 답이 나올 때까지 반복한다.

 

해당 방식은 이진탐색 O(log n)에 매 반복마다 갯수를 세는 과정 O(n)을 시행해서 최종적으로 O(n log n)의 시간복잡도를 가지게 된다.

 

cylic sort를 이용

원래 배열을 바꾸므로 문제의 조건에 부합하지 않지만, 흥미로운 방법이라서 가져왔다.

그림 1

그림 2

 cyclic sort는 n개의 수가 [1, n]의 범위에 있을 때, 혹은 그와 비슷할 때 사용하는 방법이다. n개의 수가 n개의 인덱스로 섞여있을 때 그림 2와 같이 순환이 있는 것을 이용한 것으로, 그림 1과 같이 들어있는 숫자의 인덱스에 있는 수와 현재 수를 자리를 계속 바꾸고, 해당 자리에 맞는 수가 들어가면 다음 수를 확인해보는 방법이다.

 

해당 방법은 O(n)의 시간 복잡도를 가지지만 원소의 범위와 원소 갯수가 같아야한다는 조건이 필요하다. 중복된 원소가 있어도 가능은 하지만, 방법이 조금 복잡해진다. 하지만 해당 문제에서는 정렬이 아니라 중복된 원소를 찾는 것이 목적이므로 상관이 없다.

 

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        idx = 0
        while idx < len(nums):
            pn = nums[idx]

            if pn == idx + 1:
                idx += 1
            elif pn == nums[pn - 1]:
                return pn
            else:
                nums[idx], nums[pn -1] = nums[pn -1], nums[idx]
        
        return 'error'

구현한 코드는 다음과 같다.

• 해당 인덱스에 들어있는 숫자가 인덱스보다 1이 크다면 제 자리에 원소가 들어간 것이므로 인덱스의 위치를 한칸 옮긴다.
• 만약 해당 인덱스에 들어있는 숫자가 인덱스를 따라가서 나온 숫자와 같다면 이미 해당 숫자는 정렬이 된 것인데, 현재 인덱스에 있는 숫자가 이미 정렬되어있단 뜻이므로 해당 숫자가 중복 숫자이므로 이를 반환해준다. 
• 둘 다 아니라면 위치를 서로 바꾸어 정렬시켜준다.

 

투 포인터를 이용한 풀이 (floyd 알고리즘)

neetcode 로드맵에서 의도한 풀이. 인덱스 0부터 들어있는 숫자를 다음 인덱스로 보고 계속 이어서 보는 것을 반복하면 해당 배열은 head를 0으로 하는 루프가 있는 연결리스트라고 볼 수 있다. 해당 배열에서의 숫자의 범위가 [1,n]이므로 해당 과정을 반복해도 0으로 가는 경우는 없으므로 head가 0이라고 확실히 할 수 있다.

 

위의 예시 중 첫 번째 예시인 nums = [1,3,4,2,2]를 연결리스트로 표현해보면 다음과 같다.

 

그래서 해당 사실을 이용해 반복되는 숫자를 어떻게 알까? 이전 문제에서 썼던 방식으로는 연결리스트가 루프한다는 사실만 알 수 있었다. 루프가 시작하는 위치를 알려면 추가적인 과정이 필요하다.

 

우선 루프의 시작점이 어디인지 수학적으로 생각해보기 위해 일직선으로 된 길이가 p, 루프의 길이가 c인 연결리스트를 생각해보자. 그리고 빠른 포인터와 느린 포인터가 만난 지점(빨간점)과 루프 시작점과의 거리를 x라고 해보자. 그러면 위의 그림과 같이 길이가 표현될 것이다.

 

이때 느린 포인터는 초록색과 같이 움직이고, 빠른 포인터는 빨간색과 같이 한바퀴를 더 돌아서 움직였을 것이다. 그러면 각 포인터들의 이동거리는 다음과 같이 나타낼 수 있다.

• slow : p + c - x
• fast : p + c + c-x = p + 2c - x

이때 2*(느린 포인터가 간 거리) = (빠른 포인터가 간 거리)이므로 2( p + c - x ) = p + 2c - x라는 수식이 성립한다. 정리해주면 p = x 라는 결과가 나온다. 따라서 일직선 구간의 길이와 포인터가 만난 지점에서 루프 시작점까지의 거리는 서로 같다. 

 

그래서 루프 시작점의 위치를 구하려면, 이전에 두 포인터 끼리 만난 점과 연결리스트 머리, 두 곳에서 동시에 출발해 다시 만나는 지점을 보면 된다.

 

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:
                return slow

 

위에서 설명한 내용을 수식으로 보면 다음과 같다.