[리트코드] Two Sum 2 - Input array is sorted(python)

리트코드, Two Sum 2 - Input array is sorted_두 수의 합 2 - 정렬된 입력 리스트

Two Sum II - Input array is sorted - LeetCode

TL;DR

• 이진 탐색(Binary search)

문제 요약

1. 1차원의 내림차순이 아닌 정렬된 정수 리스트 numbers에서 두 원소의 합이 target이 되는 index를 반환한다.
2. 합이 target이 되는 수는 동일한 index가 아닌 서로 다른 index여야 한다.
3. 리스트의 첫 번째 원소의 index는 1이다.

 

- 두 수의 합에 조건이 추가된 버전의 문제이다. 이번 문제의 경우는 내림차순이 아닌 정렬된 정수 리스트가 문제로 주어진다.

- 정렬이 된 리스트에서 두 수를 찾는 것이므로 Binary search를 수행해서 문제를 풀 수 있다. 다만, 이 때, 동일한 원소가 2번 더해지는 경우는 정답이 되어서는 안된다.

입출력 형태

입출력 예시

 

예시 2 :: 이 경우가 문제의 주의 사항 중 하나이다. 합이 6이 되는 경우는 2, 4를 고르는 것과 3을 두 번 고르는 2가지 경우가 존재한다. 하지만 문제의 조건에 따라 3을 두 번 고르는 선택지를 선택해서는 안 된다.

풀이

풀이는 Binary search를 통해 진행하였고, `bisect`를 사용한 코드와 그렇지 않은 코드 2가지 방법으로 풀어보았다.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        import bisect
        for i in range(len(numbers)):
            diff = target - numbers[i]
            # 중복된 요소를 선택하지 않도록 처리
            index = bisect.bisect_left(numbers, diff, i + 1)
            
            if index < len(numbers) and numbers[index] == diff:
                return i + 1, index + 1

 

`bisect`를 사용한 버전의 풀이이다. `bisect_left` 메소드를 사용할 때, 일반적인 binary search를 진행하듯이 `index = bisect.bisect_left(numbers, diff)`와 같이 사용하면 입출력 예시의 2번 케이스의 형태로 주어졌을 때 오답이 나올 수 있다.

 

low 바운더리를 처리하지 않은 경우

 

- 그림과 같이 입력이 주어졌을 때가 오답이 나올 수 있는 경우이다. 그림의 예시에서 중복 원소를 선택하면 안 되기 때문에 정답은 [1, 2]가 되어야 한다. 하지만 작성한 코드는 앞에서부터 순차적으로 원소를 조회하기 때문에 선택한 원소를 제외해주지 않으면 동일한 원소를 선택하게 된다. 

- bisect_left 메소드의 경우 세번째 인자로 low, 즉 binary search를 수행할 시작 인덱스를 지정할 수 있다. 이미 선택한 i번째 인덱스의 원소를 제외해주기 위해 시작 인자를 i + 1로 설정해주면 이 문제에서 벗어날 수 있다.

 

이는 `bisect`를 사용하지 않은 풀이에서도 동일하게 사용된다.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            diff = target - numbers[i]
            # 중복된 요소를 선택하지 않도록 처리
            low, high = i + 1, len(numbers) - 1
            
            while low <= high:
                mid = (low + high) // 2
                
                if numbers[mid] == diff:
                    return i + 1, mid + 1
                elif numbers[mid] < diff:
                    low = mid + 1
                else:
                    high = mid - 1

 

Binary search를 시작할 인덱스인 low를 i + 1 인덱스부터 시작하도록 작성해주었다. 이렇게 작성하면 동일한 결과를 얻을 수 있다.

 

정답에서 i + 1, mid + 1과 같은 형태로 작성한 이유는 문제에서 0번째 인덱스를 1번 인덱스로 처리하기 때문이다.