[LeetCode] Two Sum

 

 

Description

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 값으로 아래와 같이 list와 target이 주어진다.

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

output으로는  list에서 두 개의 원소를 뽑아서 더했을 때 target값이 되는 list의 인덱스를 찾아서 리턴해야 한다.

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

 

Two Pointer를 이용해서 풀어보기

 two pointer 방식을 익혀보기 위해 다음과 같이 풀었다.

class Solution:
    def twoSum(self, nums, target):
        left = 0
        right = len(nums) - 1

        if nums[left] + nums[right] == target:
            return [left, right]

        _index = {i: v for i, v in enumerate(nums)}

        nums.sort()
        result = []
        temp = []

        while left < right:

            if nums[left] + nums[right] < target:
                left += 1
            if nums[left] + nums[right] > target:
                right -= 1

            if nums[left] + nums[right] == target:

                for i, v in _index.items():
                    if v == nums[left]:
                        result.append(i)
                    if v == nums[right]:
                        result.append(i)
                    else:
                        temp.append(i)

                for dix in list(temp):
                    _index.pop(dix)

                del temp
                return sorted(set(result))

two pointer는 두 개의 포인터를 조작해서 얻는 값을 이용해 원하는 결과를 도출해내는 방식이다. 문제는 정렬된 배열에서 이용해야하는 것이다.  위의 코드를 보면 중간에 _index라는 dictionary를 선언해서 pointer를 조작해 얻는 value 값을 이용해 또 한 번 for문을 이용해 비교하는 로직을 태우기 때문에 이중 for문을 쓰나 위 방법을 쓰나 실행 속도는 별반 차이가 없지 않을까 생각하고 일단 돌려봤는데 결과는 의외였다.

이중 for문을 이용했을 때

two pointer를 이용했을 때

two pointer를 이용했을 때 메모리를 쓰는 공간은 _index를 한 번 사용해서 그런지 이중 for문 보다 더 나빠졌지만 시간 측면에서 보면 많이 개선됐다.

Runtime: 68 ms, faster than 58.43% of Python3 online submissions for Two Sum.

Memory Usage: 15.4 MB, less than 40.74% of Python3 online submissions for Two Sum.

 

완전 탐색으로 풀이하기

위의 two pointer로 풀이하는 방법은 문제를 풀다가 막혀 다른 해답을 참고하여 어떻게든 풀어내보려고 시도한 것이다. twoSum 문제를 해결하는 다른 풀이법으로는 완전 탐색이 있다.  제일 쉽게 풀이할 수 있는 방법이다. 배열 내의 모든 원소들의 합을 구하고 문제에서 요구하는 답과 일치하는 합이 있으면 리턴하는 방식이다.

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:

        for i in range(len(nums)):
            for j in range(len(nums)):
                if (i != j) and (nums[i] + nums[j] == target):
                    return [i, j]

주의할 점은 모든 원소의 인덱스들에 접근하기 때문에 인덱스의 위치가 같아지는 경우이다. 문제에서 요구하는 답이 특정 인덱스의 값을 두 번 더하여 나오는 값과 동일하다면 잘못된 케이스이다. 예를 들어 다음과 같은 경우이다.

nums = [3,3], target=6

위 상황에서는 0번쨰 인덱스를 두 번 더해도 target 값이 나오기 때문에 이 경우를 배제해야 하기 때문에 i와 j가 같지 않은 경우를 처리해줘야 한다.

사실 위와 같이 풀이한 경우 중복된 원소를 탐색하는 케이스가 발생한다. 이를 개선해보자면 이중 for문을 다음과 같이 개선하여 풀이할 수 있다.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i1, v in enumerate(nums):
        for i2 in range(i1, len(nums)):
            if (i1 != i2) and (nums[i1] + nums[i2] == target):
                return [i1, i2]

 

해시법

hashmap을 이용한 풀이법이다. for문을 순회하면서 hashmap에 해당 원소가 들어있지 않은 경우 hashmap에 원소와 원소의 인덱스를 넣어줌으로써 O(n)에 풀이하는 방법이다.

class Solution:

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        indices = {}
        for i, v in enumerate(nums):
            remainder = target - v

            if remainder in indices and indices[remainder] != i:
                return [indices[remainder], i]

            indices[v] = i

마찬가지로 중복된 인덱스의 경우를 걸러줘야하기 때문에 조건문에서 인덱스가 같은 경우를 체크하는 것에 유의해야 한다.