[ 7. 배열 ] - 두 수의 합(Two Sum)

📍 두 수의 합(two sum)

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

---

⚡️ 나의 풀이

이 책의 풀이방법은 4가지나 되지만, 제일 비효율적인 브루트 포스(brute force)밖에 떠오르지 않았다.

브루트 포스(brute force)으로 풀었던 방법은 이중 반복문을 선언하여 index를 하나씩 비교하는 방법인데, 이렇게 풀면 시간복잡도가 높아져서 효율적인 코드라고 말하기 어렵다.

 

책에 나와있는 다른 방식의 풀이는 상당히 효율적이었는데, target을 찾기위해서 index끼리 더하는것이 아니라 target에서 index값 한개를 빼고 남은 index값이 배열안에 있는지 탐색하는 방법이었다.

728x90

문제풀면서 이런 방식은 떠오르지 않았는데.. 많은 풀이방법 중에 브루트포스밖에 떠오르지 않다니 나의 실력이 많이 부족하다는게 느껴졌다! 앞서 이 문제를 풀 수 있는 방법은 4가지라고 말했는데, 다음과 같다.

 

1. 브루트 포스(brute force): O(N^2)
2. in을 이용한 탐색: O(N)
   반복문 안에서 target - 현재 i값이 배열안에 있는지 확인하고, 있다면 해당 위치의 index를 출력하는 방법이다.
3. dictionary: O(N)
   2번과 비슷한 방법으로 target - 현재 i값이 배열안에 있는지 확인하고, 있으면 value값을 출력한다. index위치를 출력해야하기 때문에 처음 {}를 선언할때 key와 value를 바꿔서 넣어준다.
4. dictionary2: O(N)

3번방식과 동일하지만 코드는 간결해진 방법이다. 그러나, 매번 비교하는 방식이 들어가있어 성능상으로 3번과 크게 다르지 않다.

 

번외로, 투 포인터로 풀 수 있는지에 대한 내용도 나와있었다.
결론적으로 이 문제는 투 포인터 방식으로 풀 수 없다. 이유는 투 포인터로 풀기 위해서는 정렬된 값이 필요하다.

 

만약 문제가 정렬된 값이 주어진다면 사용할 수 있겠지만, 정렬된 값이 주어진것도 아니고 게다가 index값을 출력하는 문제니만큼 더더욱 사용하기 제한된다. 그래도 혹시나 이와 비슷한 패턴의 문제를 풀 수도 있으니 어떻게 푸는지 방법정도는 숙지하고 있자.

 

투포인터로 접근하는 방법은 다음과 같다.

 

1. 왼쪽 포인터와 오른쪽 포인터의 값이 target보다 크다면 target에 가까워지기 위해 오른쪽 포인터를 왼쪽으로 옮긴다.
2. 왼쪽 포인터와 오른쪽 포인터의 값이 target보다 작다면 target에 가까워지기 위해 왼쪽 포인터를 오른쪽으로 옮긴다.
3. 언제까지? 왼쪽 포인터와 오른쪽 포인터의 index가 동일 할때까지
4. 만약, 왼쪽 포인터와 오른쪽 포인터의 index가 동일 하지 않은데 왼쪽 포인터와 오른쪽 포인터의 합이 target과 동일하다면? 왼쪽포인터, 오른쪽 포인터의 값을 출력하면 된다.

# 투 포인터 접근코드
def solution(s, target):
    left, right = 0, len(s)-1

    while not left == right:
        if s[left] + s[right] > target:
            right -= 1
        elif s[left] + s[right] < target:
            left += 1
        else:
            return [left, right]

 

# 1. brute force
def solution(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

# 2. use `in`
def solution(nums, target):
    for idx, val in enumerate(nums):
        find = target - val
        if find in nums[idx+1:]:
            return [nums.index(val), nums[idx+1:].index(find)+(idx+1)]

# 3. use hash
def solution(nums, target):
    hash_dic = {val: idx for idx, val in enumerate(nums)}

    for idx, val in enumerate(nums):
        find = target - val
        if find in hash_dic and hash_dic[find] != idx:
            return [idx, hash_dic[find]]

# 4. improve method 3
def solution(nums, target):
    hash_dic = {}

    for idx, val in enumerate(nums):
        find = target - val
        if find in hash_dic:
            return [hash_dic[find], idx]
        hash_dic[num] = idx