07. Two Sum

🎯 leetcode - 1. Two Sum

---

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 7번 문제
- 덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하세요.

📌 날짜

2020.01.17

📌 시도 횟수

2 try

💡 Code

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 target == nums[i] + nums[j]:
                    return [i, j]

💡 문제 해결 방법

- 그냥 모든 2쌍의 인덱스를 일일이 확인하는 방법이다.
- 정답을 찾을 때까지 계속 진행하고, 정답을 찾으면 해당 인덱스 list를 return 한다.

💡 새롭게 알게 된 점

- 위와 같이 모든 조합을 일일이 확인해보는 무차별 대입방식을 [브루트 포스]라고 한다.
- 브루트 포스 방법의 시간 복잡도는 O(n^2)이다.
- 아래 나오는 방법들 중 가-장 느리다. 좀 지나치게 느리다.

❌ (한번에 맞추지 못한 경우) 오답의 원인

- 처음에는 for문 맨 처음에 (if nums[i] <= target)을 추가했었다.
- 왜냐하면 타겟보다 큰 수는 더해서 타겟을 만들 수 없다고 생각했기 때문이다. 
- 그런데 조건 중에 숫자가 항상 양수라는 조건은 없다. 
- 따라서 위의 if문을 넣으면 오답이 된다.
★조건 좀 잘 확인하자!!!!★

---

😉 다른 풀이

📌 하나. in을 이용한 탐색

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

💡 새롭게 알게 된 점

✔ 현재 값(num)에 대해 (target - num)이 존재하는 지 바꾸어 생각할 수 있는게 너무 신기하다👀👍

✔ in 알아보기
  - in을 이용한 방식도 사실 시간복잡도는 브루트 포스와 동일하게 O(n^2)이다.
  - 그러나 이중 for문으로 일일이 계산하는 것 보다, in 연산이 훨-씬 빠르다.
  - in을 잘 사용하도록 하자~!

---

📌 둘. dict와 in 사용하기

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        # 일단 숫자를 키로, 인덱스를 value로 갖는 새로운 dict 만들기 
        for i, num in enumerate(nums):
            nums_map[num] = i
            
        # 현재 숫자(num)에 대하여 (target - num)이 자신을 제외한 다른 값으로 존재하는지
        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]

💡 새롭게 알게 된 점

✔ dict와 in
- ex) n in dict
위의 코드는 dict에서 값이 n인 키가 있는 지 확인하여 boolean을 반환한다.

✔ in의 시간 복잡도
- in으로 검사할 대상을 따로 dict로 빼서 검사하면 시간복잡도는 O(n)이 된다.

파이썬에서 in의 시간복잡도

• list, tuple : $O(n)$
• set, dictionary : $O(1)$
  • 딕셔너리는 해시테이블로 구현되어 있다.
  • 따라서 해시를 통해 저장 및 접근하므로 평균적으로 O(1)에 가능하다.

---

📌 셋. 더 최적화하기(정답 발견하면 즉시 return)

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

💡 새롭게 알게 된 점

-

---

👀 참고로...

• 동일한 알고리즘임에도 C++, Go 언어로는 잘 풀리는데 파이썬에서는 타임아웃이 발생하는 경우도 있다. 언어의 선택은 실행 속도에 매우 중요한 영향을 미친다. 따라서 만약 파이썬 풀이에서 계속해서 타임아웃이 발생한다면 다른 언어로 재작성하여 적절히 대응할 수 있어야 한다!