[알고리즘/Python] 219. Contains Duplicate II

📑 1. 문제 이해

https://leetcode.com/problems/contains-duplicate-ii/

Contains Duplicate II - LeetCode

배열의 서로 다른 인덱스 중 두 인덱스 차이가 k보다 작으면서 그 값이 같은 인덱스 쌍이 존재하는지 확인하는 문제이다. 

- 배열은 빈 배열일 수 없고 최대 길이가 10 *5 이다.

- 배열의 원소는 음수를 포함할 수 있다.

- k = 0일수도 있다.

☑️ 테스트케이스

문제에서 주어진 테스트 케이스는 다음과 같다.

 

Example 1:  nums = [1,2,3,1], k = 3

    - 값이 같은 원소의 인덱스차가 정확히 3 이다.

Example2: nums = [1,0,1,1], k = 1

    - 값이 같은 원소가 3개이지만, 그 인덱스 차가 k이하인 쌍은 한 쌍이다.

Example3: nums = [1,2,3,1,2,3], k = 2

    - 값이 같은 원소가 존재하지만 그 인덱스 차가 k보다 크다.

 

주의해야할 테스트 케이스는 다음과 같다.

num = [1], k = 1

   - 배열의 길이가 1이다. 서로 다른 인덱스 쌍이 존재하지 않는다.

num = [1,1,1,1], k = 0

   - k가 0이다. 자기 자신과 인덱스가 같으므로 항상 False가 반환되어야한다.

num = [1,1,1], k = 1

    - 조건을 만족하는 해가 여러개이다. 

💡 2. 알고리즘 설계 - 딕셔너리 활용

 만약 정확히 인덱스 차가 k인 인덱스 쌍을 구해야했다면 k만큼 떨어진 투 포인터를 오른쪽으로 이동키면서 값이 같은 경우가 있는지 확인하면 된다. 하지만 이 문제에서는 인덱스가 k이하인 경우를 모두 살펴봐야함으로 투포인터 방식을 사용하기 어렵다. 게다가 Brute Force로 모든 경우를 살펴본다고 하면 O(N^2) 복잡도가 되어 매우 비효율적인 알고리즘이 될 수 있다.

 이 경우에는 딕셔너리 자료형에 {값: 인덱스 리스트} 형태로 저장해 같은 값을 가지는 인덱스들을 그룹핑할 수 있다. 그 가운데 인덱스의 차가 k이하인 경우가 있는지 확인하면 된다.

 

1. k가 0이면 항상 False이기 때문에 바로 함수를 종료한다.

2. 배열을 순회하면서 {값:인덱스 리스트}를 가지는 딕셔너리를 만든다.

3. 딕셔너리의 엔트리들을 순회하면서 인덱스 차가 k이하가 되는지 확인한다. 그러한 쌍이 있으면 True를 반환한다.

4. 반복문들 모두 수행하고 종료한다면 조건을 만족하는 쌍을 찾지 못한 것으로 False를 반환한다.

class Solution:
    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        if k == 0:
            return False
        d = defaultdict(list)
        for i, x in enumerate(nums):
            d[x].append(i)

        for num, indices in d.items():
            if len(indices) < 2:
                continue
            for i in range(1, len(indices)):
                if indices[i] - indices[i - 1] <= k:
                    return True
        return False

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 배열을 딕셔너리로 만드는데 O(N), 딕셔너에 저장된 엔트리를 확인하는데 O(N)이 걸린다.

공간 복잡도: O(N). 배열의 모든 원소가 저장되어있는 딕셔너리가 필요하다.

 

⚒️ 3. 최적화

 딕셔너리를 만들고난 후 인덱스들을 검사하면 조건을 만족하는 인덱스 쌍이 앞에 위치하든, 뒤에 위치하든 무조건 O(N)시간이 걸린다. 예를 들어 nums = [1,1,2,2,2,2,2,2,2,2....]이고 target = 1일때 인덱스 쌍 [0,1]이 조건을 만족하지만 딕셔너리를 만들기 위해 모든 배열을 순회한 후 그 쌍을 찾을 수 있다. 이는 불필요한 연산이다.

 딕셔너리에 모든 인덱스가 아니라 최근에 등장한 인덱스만을 저장하면서 조건을 만족하는지 확인하면 불필요한 연산을 줄일 수 있다. 조건을 만족하는 해를 찾기 위해서는 같은 값을 가지는 원소들의 인덱스가 필요하다.  그 중에서도 가장 가까이 있는 인덱스가  필요하다. 직전에 같은 값을 가지는 인덱스와의 차가 k보다 크다면 그보다 더 멀리 떨어진 인덱스와의 차는 k보다 항상 크기 때문이다. 이를 통해 조건을 만족하는 쌍을 찾으면 바로 함수가 종료되어 배열의 끝까지 순회하지 않아도 된다. 

    def containsNearbyDuplicate(self, nums: List[int], k: int) -> bool:
        if k == 0:
            return False
        d = dict()

        for i, n in enumerate(nums):
            if n in d:
                if i - d[n] <= k:
                    return True
            d[n] = i
        return False

시간 복잡도: O(N). 최악의 경우 배열을 모두 순회해야함으로 여전히 O(N)이다. 하지만 많은 경우에 실제 연산횟수를 줄일 수 있다. 

공간 복잡도: O(N). 최악의 경우 배열의 모든 원소가 저장되어있는 딕셔너리가 필요하다.

 

⎌ 4. 검토

위에서 살펴본 테스트케이스를 검토해보면 다음과 같다.

 

Example 1:  nums = [1,2,3,1], k = 3

    - 값이 같은 원소의 인덱스차가 정확히 3 이다. d[1] = 0인 상태에서 i - d[i]를 검사하면 3이 되므로 True를 반환한다.

Example2: nums = [1,0,1,1], k = 1

    - 값이 같은 원소가 3개이지만, d[1] = 0이 저장된 상태에서 인덱스 2를 검사하면 그 차가 2가 넘어서 d[1] = 2로 값이 갱신된다. 그 후에 인덱스 3과 비교하면 조건을 만족하므로 True가 반환된다.

Example3: nums = [1,2,3,1,2,3], k = 2

    - False가 반환된다.

 

num = [1], k = 1

   - d[1] = 0에 저장한 후 for문이 종료된다. False가 반환된다.

num = [1,1,1,1], k = 0

   - k가 0이면 for문을 수행하기전 바로 False가 반환되며 함수가 종료된다.

num = [1,1,1], k = 1

    - 처음 조건을 만족하는 쌍 [0,1]을 검사한 후 True를 반환하고 종료된다. 조건을 만족한 쌍을 하나라도 찾으면 함수가 종료된다.

---

✅ 정리

◎ 배열을 딕셔너리 형태로 변형시켜 사용할때는, 딕셔너리에 모든 원소를 저장한 후에 요구되는 연산을 수행할 수도 있지만, 딕셔너리에 원소들을 저장해가면서 동시에 요구되는 연산을 수행할 수 있다. 이를 통해 불필요한 연산을 줄일 수 있다.

◎ 딕셔너리에 정말로 모든 원소가 저장되어야하는지 생각해보자.