리트코드(LeetCode) 1번 두 수의 합(Two Sum)

---

📌  풀이 1 : 브루트 포스

하나하나 다 때려 박아 비교하는 브루트 포스 방법이나

매우 널리 알려진 방법이나 시간이 매우 오래 걸린다.

리트코드 기준 4836 ms의 시간이 걸렸다.

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]

 

2중 for문으로 하나하나 비교하여 target과 같아지는 순간 인덱스들을 출력하면 된다.

 

 

---

 

 

📌  풀이 2 : 파이썬 내장 함수 in 사용

파이썬 내장함수 in을 사용하는 방법이다.

파이썬의 in함수는 시간 복잡도가 O(N)이다. 그래서 위의 브루트 포스보다 훨씬 시간이 단축됨을 확인할 수 있었다.

리트코드 기준 847 ms의 시간이 걸렸다.

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

 

enumerate를 사용해 nums의 index와 값을 출력해주고 target - n을 lest로 지정해줘 현재 비교하는 i번째 원소 이후에 lest가 있다면(여기서 파이썬 내장 함수 in을 사용)

n의 인덱스와 해당 lest의 인덱스를 출력해주는 것이다

 

 

 

 

---

 

 

 

풀이 3 해시 테이블 사용

해시 테이블 즉 파이썬에서는 딕셔너리를 사용하는 방법이다.

여기서 key와 value를 바꾸어서 새로운 딕셔너리에 저장한다는 발상을 하기 어려운데 이것만 생각해 낸다면 매우 빠른 시간 복잡도로 풀어낼 수 있다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[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[i, nums_map[target-num]]

 

🚫 조심할 점

여기서 하나 조심해야 할 점은 만약 nums가 [3, 3] 이고 target = 6 이런 식으로 3 + 3 = 6이 가능한 경우이다. 

이럴 경우 i != nums_map [target-num]이라는 조건이 없다면 [0, 0]이 출력된다. 

num이 이미 3으로 사용되었는데 target-num in nums_map이 3을 또 찾아내 갖은 인덱스를 두번 출력하는 것이다. 

이를 조심하도록 하자