[알고리즘/Python] LeetCode 167. Two Sum 2 - Input Array Is Sorted

📑 1. 문제 이해

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan-v2&envId=top-interview-150

Two Sum II - Input Array Is Sorted - LeetCode

 이 문제는 오름차순으로 정렬된 배열에서 합이 target이 되는 서로 다른 원소 쌍을 구하는 문제입니다. 항상  합이 target이 되는 오직 하나의 쌍이 존재하며 이때 중복된 원소가 있을 수 있습니다. exactly one solution이 존재한다고 해서 중복된 원소가 존재하지 않는 것은 아닙니다. [-1,-1,1,1,1,1]에서 합이 2가 되는 쌍을 찾는 경우 중복된 원소가 존재하지만 정답은 [-1,-1]로 정확히 한 쌍만 존재하기 때문입니다.

 또한 주의해야 할 점은 결과를 반환할때 인덱스의 시작을 1로 봐야한다는 것입니다.

☑️ 테스트케이스

문제에 의해 주어진 테스트 케이스는 다음과 같습니다.

 

1) Example 1: numbers = [2,7,11,15], target = 9

    - 배열의 모든 원소가 양수입니다.

2) Example 2: numbers = [2,3,4], target = 6

    - 배열의 모든 원소가 양수입니다.

3) Example 3: numbers = [-1,0], target = -1

    - 음수인 원소가 존재하고 서로 다른 원소쌍이 단 하나입니다. 

 

추가해서 테스트해볼 케이스는 다음과 같습니다

 

4) numbers = [-1, 1, 2, 2, 2, 2] target = 0

- 중복된 원소가 존재합니다.

5) numbers = [-1, -1, 2, 2, 2, 2] target = 2

- 중복된 원소가 존재하며, 값이 같은 두개의 원소를 더해서 target이 됩니다.

💡 2. 알고리즘 설계

어떤 원소 x에 대응되는 원소쌍 target -x 를 찾아야하는데 주어진 배열이 오름차순 정렬된 배열이라는 점에서 이진탐색을 떠올릴 수 있습니다.

 

1. 배열을 순회하면서 i번째 원소와 더한 값이 target이 되는 원소 goal을 찾습니다. 이때 탐색 범위는 i + 1번째 이후 원소부터입니다. index1 < index2이고, index1 + index2= target이라면 index1을 기준으로 자신보다 오른쪽 원소들을 탐색시 index2가 탐색되므로, index2를 기준으로 탐색시에는 자신보다 왼쪽의 원소들을 탐색범위에서 제외시킬 수 있습니다. 이를 통해 탐색시 검색 범위를 줄일 수 있습니다. 

2. 이진 검색을 통해 goal을 찾습니다. 탐색 범위의 가운데 원소 값이 goal을 기준으로 큰지, 작은지에 따라 탐색범위를 반으로 줄여가며 goal을 발견할때까지 이진 탐색을 진행합니다.

    - goal을 발견한다면 goal이 위치하는 index를 반환합니다.

    - 전체 범위를 탐색했는데도 goal을 발견하지 못하였다면 원소가 존재하지 않는다는 의미로 -1을 반환합니다.

3. 이진 탐색의 결과가 -1이 아니라면 해당 원소 쌍의 인덱스를 반환합니다. 이때 실제 배열의 인덱스가 아니라 1-based 인덱스를 반환하기 위해 1을 더해줍니다.

def solution(numbers: List[int], target: int) -> List[int]:
    def binary_search(left, right, goal: int):
        while left <= right:
            mid = (left + right) // 2
            if numbers[mid] == goal:
                return mid
            elif numbers[mid] > goal:
                right = mid - 1
            else:
                left = mid + 1
        return - 1

    for index, n in enumerate(numbers):
        goal = target - n
        result = binary_search(index + 1, len(numbers), goal)
        if result != -1:
            return [index + 1, result + 1]

시간 복잡도 및 공간 복잡도

시간 복잡도: O(NLogN). 전체 배열을 순회하면서 각 원소에 대해 이진탐색을 진행합니다. 이진탐색은 매번 탐색범위를 반으로 줄여가므로 탐색 범위의 원소의 개수가 N개일때 최대 LogN번의 탐색이 이뤄집니다. 이때 탐색범위는 자신보다 큰 원소들을 대상으로 하므로 범위가 1씩 줄어드므로 이진 탐색을 위한 연산 횟수는 다음과 같습니다. Log(N-1) + Log(N-2) + Log(N-2) + ... + Log(1). 따라서 빅오 표현식에 의한 총 시간 복잡도는 O(NlogN)이 됩니다.

공간 복잡도: O(1). 주어진 배열을 대상으로 이진 탐색을 하며, 이진 탐색시마다 result, mid, left, right등 변수를 위한 공간만 필요합니다. 

 

⚒️ 3. 최적화

  중복된 원소에 대해서 이미 한번 이진 탐색을 진행했다면 조건에 맞는 쌍이 존재하지 않는다는 의미이므로 다시  탐색을 할 필요가 없습니다. 한번 탐색한 원소들을 기록하기 위해서 set 타입의 변수를 활용하였습니다. set는 해시를 이용하여 검색하므로 검색시 O(1) 상수시간이 걸립니다.

    visited = set()
    for index, n in enumerate(numbers):
        if n in visited:
            continue

        visited.add(n)

        goal = target - n
        result = binary_search(index + 1, len(numbers) - 1, goal)
        if result != -1:
            return [index + 1, result + 1]

 

 간단한 연산 추가만으로도 실행속도가 160ms -> 120 ms로 훨씬 빨리짐을 확인할 수 있습니다. 다만 최악의 경우 visited변수에 N개의 원소가 모두 저장될 수 있다는 단점이 있습니다.

⎌ 4. 검토

테스트 케이스를 검토해보면 다음과 같습니다.

 

4) numbers = [-1, 1, 2, 2, 2, 2], target = 0

- 중복된 원소가 있는 경우에 이진 탐색 진행시 여러개의 중복된 원소 중 랜덤하게 하나만 검색되지만, 문제의 조건에 의해서 중복된 원소가 정답이 되는 경우는 없습니다. 따라서 이진 탐색을 진행할 수 있습니다. 

---

🤔 다른 사람의 풀이

투포인터를 이용해서 간단하게 더 빠르게 탐색할 수 있습니다. 양쪽 끝에 포인터를 두고 시작해서 두 수의 합이 target보다 크다면 두 수의 합을 줄여주기 위해 오른쪽 포인터를 왼쪽으로 한칸 이동합니다. 두 수의 합이 target보다 크다면 왼쪽 포인터를 오른쪽으로 한칸 이동해 더 큰 수를 가리키도록 합니다.

    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        start = 0
        end = len(numbers) - 1
        while start < end and numbers[start] + numbers[end] != target:
            if numbers[start] + numbers[end] > target:
                end -= 1
            else:
                start += 1
        return [start + 1, end + 1]

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 두 포인터는 교차되지 않으며 두 포인터의 이동횟수의 합은 배열의 길이를 넘지 않습니다.

공간 복잡도: O(1). 포인터 두개만 추가로 필요합니다.

 

---

✅ 정리

◎ 이진탐색이 탐색이 빠른 알고리즘이지만, 모든 원소에 대해서 각각 이진 탐색을 진행하면 NLogN이 되어 오히려 비효율적일 수 있습니다. O(N)으로 전체 배열을 순회하는 것이 오히려 더 빠를 수 있습니다. 

◎ 일정한 규칙으로 정렬된 배열에서 두 수의 쌍을 찾고자 할때 투 포인터를 사용해서 효율적으로 탐색하는 방법을 찾아보는것이 좋습니다.

 

 

 

 

 

https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/?envType=study-plan-v2&envId=top-interview-150

Two Sum II - Input Array Is Sorted - LeetCode