LeetCode1 - Two Sum

lc.leetcode

1. Brute-Force

배열에서 인덱스를 찾을 때 brute-force(무차별 대입)를 이용하면 간단하게 찾아낼 수 있다. 하지만 매우 비효율적이기 때문에 더 최적화할 수 있는 방법을 찾아야 한다.

class Solution:
    def twoSum(self, nums: list, target: int):
        for i in range(len(nums) - 1):
            for j in range(i+1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

for문이 두 번 사용됐으니 시간 복잡도는 O(n^2)이다.

2. in을 이용한 탐색

in의 시간복잡도는 O(n)이고 for문 안에서 돌리기 때문에 brute-force와 동일한 O(n^2)의 성능을 낸다.
하지만 같은 시간 복잡도라도 파이썬의 내부함수로 구현된 in 연산이 더 빠르고 가볍다.

모든 조합을 비교하지 않고, target - n이 배열에 존재하는지 탐색하면 더 빠르게 index 값을 찾아낼 수 있다.

class Solution:
    def twoSum(self, nums: list, target: int):
        for i, n in enumerate(nums):
            complement = target - n
            
            if complement in nums[i + 1:]:
                return nums.index(n), nums[i+1:].index(complement) + (i + 1)

3. 해시값 조회

Dictionary는 hash table로 구현되어 있기 때문에 Key값 조회는 평균적으로 O(1)에 가능하다.

enumerate()를 사용하여 Dictionary에 key와 value를 삽입하는데, 서로 바꿔서 저장하면, value를 key로 사용하여 검색할 수 있다.

class Solution:
    def twoSum(self, nums: list, target: int):
        nums_map = {}
        
        for i, num in enumerate(nums):
            nums_map[num] = i
            
        for i, num in enumerate(nums):
            if target - num in nums_map and i != nums_map[target -num]:
                return nums.index(num), nums_map[target - num]

두 개의 for문을 하나로 줄이는 구조 개선 코드

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