[파이썬 알고리즘] 7장 배열 - 두 수의 합 (two-sum)

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

Two Sum - LeetCode

 

<문제>

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

 

<예시>

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

Output: Because nums[0] + nums[1] == 9, we return [0, 1].

 

---

def my_solution(nums: list, target: int) -> list:
    # 가장 비효율적인 풀이법
    # 문제가 풀리기는 하지만, 좀 더 최적화 할 수 있는 방법을 고민해야 한다.
    length = len(nums)
    for i in range(length):
        for j in range(i+1, length):
            if nums[i]+nums[j] == target:
                return [i, j]

 

def solution_3(nums: list, target: int) -> list:
    num_to_index = {}
    # O(n)
    for i, num in enumerate(nums):
        num_to_index[num] = i # key: 값, value: index

    # O(n)
    for i, num in enumerate(nums):
        if target-num in num_to_index and i != num_to_index[target-num]:
            # return [nums_dict[num], nums_dict[target-num]]
            # 라고 하면 nums로 [3, 3]과 같이 같은 값이 들어오는 경우 fail
            # 동일한 key, 다른 value는 저장될 수 없다는 것 기억
            return [i, num_to_index[target-num]]

 

 

def if_solution(nums: list, target: int) -> list:
    # two-pointer를 이용한 풀이
    # 이러한 풀이는 list가 정렬되어 제공될 때 가능하다.
    # 여기서는 원본 list의 "index"를 반환하여야 하기 때문에 list 정렬 후 다음 풀이를 적용해도 X
    head_index = 0
    tail_index = len(nums)-1
    while tail_index < head_index:
        if nums[head_index]+nums[tail_index] == target:
            return [head_index, tail_index]
        elif nums[head_index]+nums[tail_index] > target:
            # target보다 크다면 tail_index를 왼쪽으로 이동
            head_index -= 1
        else:
            # nums[head_index]+nums[tail_index] < target
            # target보다 작다면 head_index를 오른쪽으로 이동
            tail_index += 1
    return [-1, -1]

 

가장 비효율적인 코드는 O(n^2)이다.

 

 

<알게된 것>

• two pointer를 활용한 풀이방법
  • 위의 문제에서는 사용할 수 없지만, 배열 관련해서 two pointer 이용한 문제풀이가 다수 존재한다.
  • 어떻게 적용할 지 고민해보는 것이 좋을 것 같다.
• 개인적으로 solution_3이 O(n^2)에서 O(n)으로 풀이하기 위한 여러 시도가 보여서 좋았다.