[LeetCode] 1. Two Sum (두 수의 합)

🔦 문제 링크

🔊 파이썬 알고리즘 인터뷰 책을 참고했습니다.

• 문제

덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라

✍️ 풀이

---

• 브루트 포스 풀이 방법
• 파이썬 in을 이용한 좀 더 빠른 풀이

target 숫자에서 숫자 하나를 빼는 것에 해당하는 원소를 찾는 방법이다. 이는 in을 이용할 수 있기에 조금 더 빠르다.또한 딕셔너리 구조를 사용했기 때문에 O(1) 의 속도로 탐색이 가능하다.

🛠 코드

• 리스트를 원소를 앞-뒤로 검사하는 가장 기본적인 풀이방법이다.

---

• 기본 브루트포스 풀이 방법

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

• in 속도 향상

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

• in과 딕셔너리를 이용해 조회 구조 개선한 코드

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

📝 정리

---

• 투 포인터는 해당 문제에 적용이 불가하다. 이유는 해당 문제를 값이 아닌 인덱스를 찾기 때문에 정렬할 수 없기 때문이다. 정렬을 하게 되면 각각의 인덱스 위치도 변화하므로 답을 낼수 없다. 그러나 투 포인터는 정렬된 상태에서만 진행할 수 있다.

🎈 참고

---

Book 링크