Two Sum

이번에는 배열과 HashMap의 대표적인 문제인 Two Sum 문제를 풀어보겠습니다. 

문제 난이도는 쉬운 편에 속하지만 다양한 방법으로 풀 수 있는 방법이 있기 때문에 정확하게 이해하시는 것이 좋습니다.

문제

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

Two Sum - LeetCode

 

위 문제는 배열을 순회하는 대표적인 문제입니다. 서로 다른 두 원소를 더해서 target이 나오는 경우를 찾으면 됩니다.

가장 간단한 방법으로는 모든 경우를 다 조사하는 것입니다. 이를 Brute Force(브루트 포스) 알고리즘이라고 합니다.

 

Brute Force 알고리즘을 사용하면 다음과 같이 풀 수 있습니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # i번째 원소를 선택합니다.
        for i in range(len(nums)):
            # i+1번째 원소부터 끝까지 하나씩 확인하면서 두 수의 합이 Target과 같아지는 경우를 찾습니다.
            for j in range(i+1, len(nums)):
                # 만약 두 수의 합이 Target과 같으면 그 원소들의 인덱스를 리스트로 반환합니다.
                if (nums[i] + nums[j] == target):
                    return [i, j]
        return []

 

문제에서는 반드시 한가지 경우가 존재한다고 했기 때문에 찾는 즉시 바로 정답을 반환하시면 됩니다. 

하지만 이렇게 풀면 O(N^2)만큼의 시간복잡도가 발생합니다. 만약 리스트의 길이가 커지면 시간은 제곱만큼 늘어나게 됩니다.

 

어떻게 하면 조금 더 빠르게 정답을 구할 수 있을까요?

 

힌트는 바로 i번째 원소를 사용하기로 결정한 순간 우리가 구해야하는 숫자를 정확히 알 수 있다는 점입니다. 이 문제의 목적은 두 수를 더해서 Target Number가 되는 두 요소를 찾는 것인데, 우리가 하나의 원소(A)를 고정하면 다른 원소의 값은 Target - A 가 됩니다. 즉, 나머지 모든 원소를 매번 순회하지 않고, 해당 숫자가 다른 곳에 있는지만 확인하면 됩니다. 

 

그러면 우리에게 필요한 것은 이전에 어떤 숫자가 있었는지 판별하는 기능입니다. 이는 HashMap을 활용하면 손쉽게 구현할 수 있습니다.

전체 풀이를 보면 아래와 같습니다.

 

1. 처음부터 끝까지 i번째 원소를 사용하기로 하고 고정합니다.

2. Target - nums[i]를 통해 찾아야하는 수를 구합니다.

3. 이전에 저장된 값들 중에서 2번에서 찾은 수가 있는지 확인합니다.

   - 만약 원하는 값이 i번째 이후에 있어도 상관 없습니다. 왜냐하면 1번에서 처음부터 끝까지 순회한다고 했기 때문에, 뒤에 원소가 i번째 원소가 되면, 현재 값을 찾게 될 것이기 때문입니다. 예를 들어 [1,2,3,4,5] 에서 Target 번호가 6이라고 한다면, i번째 원소가 1번일때는 정답을 찾지 못하지만, i번째 원소가 5번째 원소일때 이전에 1이 있었던 것을 찾을 수 있습니다. 따라서 1번에서 굳이 뒤에 있는 원소를 고려할 필요가 없습니다.

 

4. 만약 정답이 되는 원소가 있으면 그 값의 인덱스와 i를 리턴합니다.

5. 원소가 없으면, 현재 i번째 값을 Key, i 를 Value로 HashMap에 저장합니다. 즉, 실제 값이 Key가 되고, 인덱스가 Value가 됩니다.

 

 

위 순서로 문제를 풀어보면 아래와 같습니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        # i번째 원소를 선택합니다.
        for i in range(len(nums)):
            # 찾아야 하는 값을 구합니다.
            need_to_find = target - nums[i]
            
            # 만약 찾고자 하는 값이 이미 hashmap에 있으면 정답을 리턴합니다.
            if need_to_find in hashmap:
                return [hashmap[need_to_find], i]
            
            # 없으면 현재 정보를 hashmap에 등록합니다.
            hashmap[nums[i]] = i
        return []

 

---

비슷한 문제 풀어보기

위 문제를 정확하게 푸셨으니 이와 비슷한 문제도 풀어보겠습니다.

 

유사 문제 1

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/

Two Sum II - Input Array Is Sorted - LeetCode

 

이번에는 배열이 이미 정렬된 상태라는 특수한 조건이 주어졌습니다. 이 배열은 위에서 다뤘던 문제의 특별한 케이스를 다룬 것이기 때문에 위에서 통과했던 코드를 그대로 사용해도 Accept를 받으실 수 있습니다.

 

※ 다만 주의하실 점은 이번 문제는 배열의 인덱스가 아닌 원소의 차례 번호를 반환해야하기 때문에 인덱스 값에 1을 더해야 합니다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hashmap = {}
        # i번째 원소를 선택합니다.
        for i in range(len(nums)):
            # 찾아야 하는 값을 구합니다.
            need_to_find = target - nums[i]
            
            # 만약 찾고자 하는 값이 이미 hashmap에 있으면 정답을 리턴합니다.
            if need_to_find in hashmap:
                
                # 이번에는 배열의 인덱스가 아니라 순서를 반환해야 하므로, 인덱스 값에 1을 더해야 합니다.
                return [hashmap[need_to_find] + 1, i + 1]
            
            # 없으면 현재 정보를 hashmap에 등록합니다.
            hashmap[nums[i]] = i
        return []

 

하지만 이번 문제가 특별한 이유는 바로 HashMap을 사용하지 않고도 문제를 풀 수 있다는 점입니다. 즉, 이전에 어떤 정보가 있었는지 알 필요가 없다는 의미입니다. 이것이 가능한 이유는 바로 배열이 정렬되어 있기 때문입니다.

 

예를 들어서 배열 [1,2,3,4,5,6,7,8] 에서 임의의 두 원소를 정했다고 가정해 보겠습니다. 

첫번째 원소는 2, 두번째원소는 7 이라고 가정하겠습니다. 만약 저희가 찾아야하는 값이 12라고 하면, 7 + 2 = 9 < 12 이므로 정답이 될 수 없습니다. 여기서 두번째원소 7 입장에서는 2보다 작은 원소들을 굳이 확인할 필요가 없습니다. 즉, 7입장에서는 2보다 큰 수가 필요하기 때문에 첫번째 원소를 오른쪽으로 한 칸 옮겨서 3을 사용해보는 전략을 사용하는 것이 현명합니다. 따라서 2 이전에 1이 있던 0이 있던 상관 없기 때문에 굳이 hashmap에 이전 정보를 저장할 필요가 없습니다.

 

이 문제는 가장 왼쪽 원소와 가장 오른쪽원소를 가리키는 두 포인터를 사용해서 조건에 따라 포인터를 움직여주는 Two Pointers 패턴을 사용하여 풀 수 있습니다. Two pointers를 사용할 수 있는 이유는 포인터를 한 번 옮기면 다시 돌아갈 일이 없기 때문입니다.

 

알고리즘을 설명하면 아래와 같습니다.

1. 배열의 가장 왼쪽 원소를 left 포인터, 오른쪽 원소를 right 포인터로 지정합니다.

2. 만약 left 포인터의 값과 right 포인터의 값의 합(Sum)이 Target이랑 일치하면 [left + 1, right + 1] 을 반환합니다.

3. 만약 Sum < target 이면, 더 큰 값이 필요하므로 left 포인터를 한칸 오른쪽으로 이동합니다.

4. 만약 Sum > target 이면, 더 작은 값이 필요하므로 right 포인터를 한칸 왼쪽으로 이동합니다.

 

코드는 아래와 같습니다.

 

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        left = 0 # 가장 왼쪽 원소를 가리키는 포인터
        right = len(nums)-1 # 가장 오른쪽 원소를 가리키는 포인터
        while left < right: # 두 포인터가 만나기 전까지 과정을 반복
            sum_value = nums[left] + nums[right]
            
            # 만약 두 값의 합이 같다면 정답을 반환합니다.
            if sum_value == target:
                return [left + 1, right + 1]
            
            # 만약 합이 target보다 작으면 더 큰 원소가 필요하기 때문에
            # left를 한 칸 오른쪽으로 옮깁니다.
            elif sum_value < target:
                left += 1
                
            # 만약 합이 target보다 크다면 더 작은 원소가 필요하기 때문에
            # right를 한 칸 왼쪽으로 옮깁니다.
            else:
                right -= 1
        return []

 

유사 문제 2

이번에는 배열이 아니라 트리에서 동일한 문제를 풀어보겠습니다.

https://leetcode.com/problems/two-sum-iv-input-is-a-bst/

Two Sum IV - Input is a BST - LeetCode

 

문제를 보시면 Binary Search Tree 내에서 두 수의 합이 K가 되는 경우가 있는지를 판별하는 문제입니다. BST라고 어려워하실 필요가 전혀 없습니다.

 

BST의 성질 중 가장 중요한 것은 아래와 같습니다.

1) 자신보다 왼쪽에 있는 모든 노드의 값은 자신의 값보다 작습니다.

2) 자신보다 오른쪽에 있는 모든 노드의 값은 자신의 값보다 큽니다.

3) 자신의 왼쪽 및 오른쪽 트리도 BST 조건을 만족합니다.

 

즉, 왼쪽 -> 자신 -> 오른쪽 순서로 트리를 순회하면, 마치 정렬된 배열을 처음부터 끝까지 순회하는 것과 같습니다. 다만 유사문제 1번처럼 두 포인터를 활용할 수는 없습니다. 왜냐하면 Tree에서 부모를 가리키는 변수가 따로 정의되어 있지 않기 때문입니다. 따라서 원래 문제와 같이 hashmap을 사용하여 이전에 나온 값들이 hashmap에 넣고, 자신의 순서가 왔을때 (K - 자신의 숫자) 값이 HashMap에 있으면 True를 반환합니다.

 

코드는 아래와 같습니다.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    # hashmap을 사용하기 위해 helper 함수를 사용합니다.
    def findTargetHelper(self, root, k, hashmap):
        # 만약 root가 비어 있으면 False를 반환합니다.
        if not root:
            return False
        
        # 자신의 왼쪽에서 이미 찾았으면 True를 리턴합니다.
        if self.findTargetHelper(root.left, k, hashmap):
            return True
        
        # 자신보다 왼쪽에 있는 모든 원소는 hashmap에 등록되어 있기 때문에 
        # 배열이 정렬되어 있는 문제와 동일합니다.
        if k - root.val in hashmap:
            return True
        
        # 현재 노드의 값을 HashMap에 등록합니다.
        # 값은 1이 아니라 아무 값이나 들어가도 됩니다.
        hashmap[root.val] = 1
        
        # 현재 노드에서 못찾았다면 오른쪽 결과를 그대로 반환합니다.
        return self.findTargetHelper(root.right, k, hashmap)
        
    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        return self.findTargetHelper(root, k, {})

 

---

심화문제 풀어보기

심화 문제 1

이번에는 두 값의 합이 아니라 세 값의 합이 Target과 같아지는 경우를 찾는 문제입니다.

https://leetcode.com/problems/3sum/

3Sum - LeetCode

 

 

이번 문제는 이전 문제에서 하나 더 숫자가 늘어난 경우입니다. 하지만 기본적인 원리는 동일합니다. 왜냐하면 Three sum을 Two sum으로 바꿀 수 있기 때문입니다. 그 방법은 하나의 숫자를 지정하고, 나머지 숫자 중 두 수의 합이 (-첫번째 숫자)가 되면 됩니다. 즉, [-1,-2,-3,1,3,5] 에서 만약 첫번째 수는 -1로 고정하면, [-2,-3,1,3,5] 중에 두 수를 더해서 1이 나오는 경우를 찾으면 됩니다. 그러면 Two sum과 같은 문제가 됩니다.

 

여기서 주의할 점은 결과값에 중복이 있으면 안됩니다. 따라서 현재 사용된 값을 이미 사용했으면 그 다음 경우의 수를 찾을 때는 이전과 같지 않을 때만 확인하면 됩니다.

 

알고리즘은 다음과 같습니다.

1. 중복 작업을 체크하기 위해서 먼저 배열을 정렬합니다. 배열된 정렬에서는 인접한 두 수가 같은지 확인하는 방법으로 중복을 확인할 수 있습니다.

2. 처음부터 끝까지 리스트를 순회하면서, 하나의 원소를 고릅니다.

3. 그 원소 이후의 리스트를 확인하면서 세 수의 합이 0이 되는 경우를 찾아냅니다.

  - 이 때 배열이 정렬되어 있기 때문에 Two Pointers 기법을 사용할 수 있습니다.

  - 다만, 이때도 이미 조건에 만족하는 경우에서 사용된 값은 중복되어 사용되면 안되기 때문에 중복되지 않는 원소를 찾는 로직이 추가되어야 합니다.

 

 

코드는 아래와 같습니다.

 

class Solution:
    def twoSum(self, nums: List[int], first_element_index: int, ret: List[List[int]]) -> List[List[int]]:
        target = - nums[first_element_index]
        
        # 왼쪽과 오른쪽 끝 포인터를 지정합니다.
        # 왼쪽은 배열의 왼쪽이 아니라 first_element_index(첫번째 수) 이후 중 가장 왼쪽입니다.
        left, right = first_element_index +1, len(nums)-1
        while left < right:
            # 두 수의 합을 구합니다.
            two_sum = nums[left] + nums[right]
            
            # 두 수의 합이 target과 같으면 정답을 추가합니다.
            if two_sum == target:
                ret.append([nums[first_element_index], nums[left], nums[right]])
                
                # 한 번 사용된 케이스는 다시 체크할 필요가 없기 때문에 왼쪽에서도 한칸, 오른쪽에서도 한칸씩 이동합니다.
                left += 1
                right -= 1
                
                # left 포인터의 값이 이전에 사용되지 않는 값이 나올 때까지 오른쪽으로 한칸씩 이동합니다.
                while left < right and nums[left] == nums[left-1]:
                    left += 1
                    continue
            
            # 두 수의 합이 작으면, 더 큰 수가 필요하므로 left 포인터를 이동합니다.
            elif two_sum < target:
                left += 1
            
            # 두 수의 합이 크면, 더 작은 수가 필요하므로 right 포인터를 이동합니다.
            else:
                right -= 1
        return ret
        
        
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ret = []
        
        # 중복 체크를 위해서 배열을 정렬합니다.
        nums.sort()
        
        # 리스트를 순회하면서 첫번째 원소를 지정합니다.
        for i in range(len(nums)):
            
            # 만약 그 값이 이미 이전에 확인한 값이면 건너 뜁니다.
            if i > 0 and nums[i] == nums[i-1]:
                continue
                
            # 이미 숫자 하나가 고정되었기 때문에 TwoSum 문제가 됩니다. Target은 -nums[i]입니다.
            self.twoSum(nums, i, ret)
            
        return ret

 

---

이번 포스트에서는 배열에서 두 수 또는 세 수의 합을 구하는 문제들을 풀어보았습니다. 이번 포스트를 통해서 아래의 개념들을 다시 한 번 점검하시는 시간을 가지시면 도움이 되실 거라 믿습니다.

• HashMap
• 정렬 알고리즘
• Binary Search Tree
• Two Pointers 패턴

 

 

개발자 취업을 희망하시는 분들은 공부 전략에 대한 포스트도 한 번 읽어보시는 것을 추천드립니다.

[개발자 취업성공패키지] 성공할수밖에 없는 실전 전략!