[알고리즘/Python] 1. Two Sum - 딕셔너리 풀이

📑 1. 문제 이해

https://leetcode.com/problems/two-sum/?envType=study-plan-v2&envId=top-interview-150 

Two Sum - LeetCode

정렬되어 있지 않은 배열의 원소 중 서로 다른 두 개의 원소를 더해 target이 되는 인덱스를 구하는 문제입니다.

- 이때 한 원소를 두번 사용할 수 없지만, 값이 중복된 원소는 있을 수 있습니다.

- 원소는 음수가 될 수 있습니다. 

- 단 하나의 해만 존재합니다.

 

☑️ 테스트케이스

Example1: nums = [2,7,11,15], target = 9

   - 배열이 정렬된 상태입니다.

Example2: nums = [3,2,4], target = 6

   -배열이 정렬되지 않은 상태입니다.

Example3: nums = [3,3], target = 6

   - 중복된 원소가 존재합니다. 

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

 BruteForce로 이중 for문으로 모든 원소 쌍을 확인해볼 수 있지만 이는 너무 비효율적입니다. 배열의 원소들을  dictionary에 원소: 인덱스 쌍으로 저장해두어 검색 효율을 높일 수 있습니다.

 이때 주의할 점은 중복된 원소가 있을 수 있다는 점입니다. 따라서 원소: 인덱스의 배열로 저장합니다.

 

1. 배열을 dictionary자료형에 원소:인덱스 쌍으로 저장합니다.

2. 다시 배열을 순회하며 n에 대해서 target - n이 배열에 존재하는지 확인합니다.

    - target -n ==n 이라면 dictionary의 값인 배열의 길이가 2인지 확인합니다.

    - target - n  != n이라면 그 값이 dictionary의 key 중에 그 값이 있는지 확인합니다.

3. 인덱스 쌍을 반환합니다.

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        d = defaultdict(list)
        for i, n in enumerate(nums):
            d[n].append(i)

        for i, n in enumerate(nums):
            if target - n != n and target - n in d:
                return [i, d[target - n][0]]
            elif target - n == n and len(d[n]) == 2:
                return d[n]

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 배열을 최대 한번 순회하며 dictionary자료형에 저장하고, 다시 한번 배열을 순회하며 더해서 target이 되는 쌍이 있는지 확인합니다.

공간 복잡도: O(N). 최악의 경우 모든 원소가 값이 다르다면 d에 배열의 길이만큼의 엔트리(키-값 쌍)가 저장됩니다.

 

⚒️ 3. 최적화 - 배열을 한번만 순회

딕셔너리에 저장하면서 동시에 대응되는 쌍이 존재하는지 확인한다면 배열을 한번만 순회하면서 더해서 target이 되는 쌍을 찾을 수 있습니다.

 def twoSum2(self, nums: List[int], target: int) -> List[int]:
        d = dict()
        for i, n in enumerate(nums):
            if target - n in d:
                return [i, d[target - n]]
            d[n] = i

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 시간 복잡도는 최악의 경우 배열을 끝까지 한번 순회해야 하므로  O(N)입니다. 다만 위의 풀이와 다르게  최대 한번만 배열을 순회하고, 대부분의 경우 반복문 중간에 값이 반환되므로  실제 연산 횟수가 줄어듭니다.

공간 복잡도: O(N). 최악의 경우 모든 원소가 값이 다르다면 d에 배열의 길이만큼의 엔트리(키-값 쌍)가 저장됩니다.

 

 ⎌ 4. 검토

테스트 케이스를 검토하면 다음과 같습니다.

 

Example1: nums = [2,7,11,15], target = 9

   - 배열이 정렬된 상태입니다.

Example2: nums = [3,2,4], target = 6

   -배열이 정렬되지 않은 상태입니다.

=> 배열이 정렬된 상태이든 아니든 딕셔너리 자료형에 저장한 후 검색하므로 모두 검색시간이 O(1)시간이 걸립니다.

 

Example3: nums = [3,3], target = 6

   - 중복된 원소가 존재합니다. 

=> 중복된 원소가 존재하여도 딕셔너리 값에 리스트로 인덱스들이 저장되므로 더해서 target이 되는 인덱스 쌍을 찾을 수 있습니다.

---

✅ 정리

◎ 배열이 일정한 규칙(오름차순 정렬 등)을 가지지 않는다면 투포인터로 해결할 수 없습니다.

◎ 이때, 검색 속도를 높이기 위해 배열을 딕셔너리로 변환할 수 있습니다. O(1)시간에 특정한 원소가 존재하는지 검색할 수 있습니다.