LeetCode 1(Two Sum, Python)

1. 문제 링크

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

2. 문제 설명

• list와 target 숫자가 주어졌을 때, list의 두 수를 더했을 때 target 숫자가 되는, index list를 반환하는 문제
• 예시) nums = [2,7,11,15], target = 9 → output [0,1]

3. 처음 풀이 

• 이중 for문을 돌려서, nums[i]와 nums[j]를 더한 게 target이면 index를 반환 

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

• runtime이 하위 29.93%, 이중 for문에 대한 개선이 필요했음 

4. 개선된 풀이 

• 이중 for문 돌리지 않고 hashmap을 사용
• nums에 for문을 돌리면서, num을 key, index를 value로 한 dict에 저장
  • 만약 dict에 target-num가 존재하면, 해당 index와 num반환 
  • 존재하지 않는다면 dictionary에 num:index 저장 
• 예시 
  • nums = [2,7,11,15], target = 9 일 때
  • 먼저 dict에 {2:0} 추가 후 target-num = 9-7 = 2 가 dict에 있으므로 2와 7의 index인 0, 1을 반환

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_indices = {}  # num을 key로 하고 index를 value로 한 dictionary 저장
        
        for i, num in enumerate(nums):
            complement = target - num
            
            # complement가 이미 num_indices dictionary에 존재하는지 체크
            if complement in num_indices:
                return [num_indices[complement], i]
            
            # dictionary 추가
            num_indices[num] = i
        
        # 위에서 return이 안되면 emtpy list 반환
        return []

5. 배운 점 

• 이중 for 문은 O(n^2)이라 complexity가 높다. 가능하면 다른 방법이 있는지 확인해보기 (여기서는 hashmap)