LeetCode - Two Sum [Python]

https://leetcode.com/problems/two-sum/

Two Sum - LeetCode

---

풀이 과정

합이 target이 되는 배열 값을 가리키는 인덱스 2개를 구하라는 문제이다.

 

완전 탐색을 돌려서 O(N^2)로 답을 구할 수 있다. 그런데 후속 조치로 O(N^2) 보다 적은 시간 복잡도를 가진 알고리즘으로 해결할 수 있냐는 질문이 달려있다.

 

1. 투 포인터로 풀기

입력된 리스트에 enumerate로 index 붙여주고, x:x[1]에 대해 정렬시킨 뒤, 포인터를 배열의 시작, 끝부분에 위치시키고 포인터에 해당하는 배열의 합이 타겟보다 작으면 left += 1, 아니면 right -= 1 시켜가면서 답을 구했다.

 

정렬이 O(NlogN)이고 투포인터로 배열 탐색이 O(N) 걸리니 알고리즘의 시간 복잡도는 O(NlogN)이다. 105ms의 실행시간을 가지는 효율적 방법이다.

 

2. 딕셔너리로 풀기

딕셔너리[값] = 인덱스를 저장해나가면서, 타겟 - 값을 키로 갖는 밸류가 딕셔너리에 존재하는지 살펴본다. 배열을 1회만 탐색하면 되므로 O(N)인데 실행시간이 112ms가 나와 투 포인터보다 의미 있게 빠르진 않았다.

---

소스 코드

투 포인터

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums) - 1
        s_nums = sorted(enumerate(nums), key=lambda x:x[1])
        
        while (left < right):
            sum = s_nums[left][1] + s_nums[right][1]
            if sum == target:
                return [s_nums[left][0], s_nums[right][0]]
                break
            elif sum < target:
                left += 1
            else:
                right -=1

 

딕셔너리

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        dic = {}
        for i, num in enumerate(nums):
            if target - num in dic:
                return [dic[target - num], i]
            dic[num] = i