리트코드 1. 두 수의 합(파이썬)

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

 

Example 1:Input: nums = [2,7,11,15], target = 9 Output: [0,1] Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6 Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6 Output: [0,1]

---

[접근 고민] 

1) for i in range(len(nums)-1) 해서 인덱스를 다 읽어줄 수 있어

          for j in nums 해서 리스트 속 원소 하나하나를 다 읽어줄 수도 있지

2) 다행히 '두 숫자' 인덱스라는 조건이 있네. 

           nums[i] + nums[i+1] == target:

               i++

           이라고 하면 ... 모든 2가지 조합을 다 비교해주지는 못하는건데? 이중 반복문에 대한 아쉬운 이해

 

* 다른 방법으로 고민comnination 사용해서 nums로 만들 수 있는 2자리 조합들을 다 만들어줌.리스트 하나씩 읽는데, 그 속의 튜플 (a, b 이런 생김새겠지)들의 합이 == target과 같다면 -> 두 수 출력

 

+인덱스 구하는 문제라 하나를 더 생각해야하네ㅠ

 

output = []

 

for i in range(len(nums)-1)

       if nums[i] == a | b: (위에서 나온 튜플 변수를 이렇게 둔다면)

             output.append(i)

---

[코드 짜기]

 

* 생각의 흐름대로 작성해본 코드... 

from itertools import combinations

def twoSum(self, target, nums):
    num_list = list(combinations(nums, 2))

    result = []
    for i in num_list:
    #  i는 지금 ( , ) 튜플 상태일 것 
        for j in i: 
            if i[j] + i[j+1] == target: 
                result.append(i)

    output = []
    for i in range(len(nums)-1):
        if nums[i] == result[0] | result[1]:
            output.append(i)

    return(output)

 

---

[올바른 코드를 확인해보자]

 

풀이 1 ) 브루트포스 

- 모든 조합을 일일히 다 확인해보는 것 (엄청나게 비효율적...) 비효율적인게 이해가 직관적으로 잘된다...ㅎㅎ 

- 무차별 대입 방식

-> "최적화하는 다른 방법을 알아봐야한다."

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) in을 이용한 탐색 (pass)

아이디어 : 모든 조합을 비교하지 않고 정답 - 타겟에서 첫 번째 값을 뺀 값 (target-n)이 존재하는지 탐색하는 문제로 변형

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)]

cf) enumerate : 열거하다.

 

풀이 3) 첫 번째 수를 뺀 결과 키 조회 (pass) 

아이디어 : 비교나 탐색 대신 한 번에 정답을 찾을 수 있는 방법은 없나?

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]]

 

풀이 4) 조회 구조 개선

def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_map = {}
        # 하나의 `for`문으로 통합
        for i, num in enumerate(nums):
            if target - num in nums_map:
                return [nums_map[target - num], i]
            nums_map[num] = i

 

풀이 5 ) 투 포인터 이용

def twoSum(self, nums: List[int], target: int) -> List[int]:
        left, right = 0, len(nums) - 1
        while not left == right:
            # 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로
            if nums[left] + nums[right] < target:
                left += 1
            # 합이 타겟보다 작으면 왼쪽 포인터를 오른쪽으로
            elif nums[left] + nums[right] > target:
                right -= 1
            else:
                return [left, right]