LeetCode의 Two Sum II - Input Array Is Sorted 문제를 함께 풀어보도록 하겠습니다.
문제
오름차순으로 정렬이 되어있는 여러 개의 정수로 이루어진 numbers 배열과 target이라는 정수가 주어졌을 때, numbers 배열 내에서 합이 target이 되는 두 개의 정수의 인덱스를 반환하는 함수를 작성하라.
단, 여기서 인덱스는 0으로 시작하지 않고 1로 시작한다.
예제
- 입력
numbers = [1, 2, 4, 6, 7, 9, 10, 11, 12]
target = 9- 결과
[2, 5]- 설명
배열 내에서 합이 9가 되는 정수는 2번째 정수인 2와 5번째 정수인 7입니다.
풀이 1
이 문제를 푸는 가장 단순무식한 방법은 이중 루프를 돌면서 배열로 부터 뽑아낼 수 있는 모든 2개 정수로 뽑아서 더해보는 것입니다.
이 알고리즘은 시간 복잡도는 O(n^2)이기 때문에 입력 배열의 크기가 커지면 커질 수록 성능이 현저하게 떨어질 것입니다.
이 풀이에 대해서는 Two Sum에서 이미 다루었으니 여기서는 그냥 넘어가겠습니다. 이 방법은 무엇보다 입력 배열이 오름차순으로 정렬되어 주어진다는 문제의 특성을 전혀 활용하지 못하므로 좋은 해결이라고 보기는 어려울 것 같습니다.
풀이 2
주어진 예제를 통해서 어떻게 하면 좀 더 효율적으로 이 문제를 풀 수 있을지 생각해볼까요?
우리는 주어진 배열 [1, 2, 4, 6, 7, 9, 10, 11, 12]에서 합이 9가 되는 정수 2개를 찾아야합니다.
먼저 배열의 첫 번째 정수인 1을 선택해보겠습니다.
1에 무엇을 더해야 9가 되죠?
네, 맞습니다. 8을 더해야 합니다.
하지만 주어진 배열에 8은 없네요.
그럼 1은 탈락…
1 2 4 6 7 9 10 11 12
👆이번에는 두 번째 정수인 2를 선택해볼까요?
2에 무엇을 더해야 9가 되죠?
네, 7을 더해야 합니다.
주어진 배열에 4번째 자리에 7이 있네요!
👇
1 2 4 6 7 9 10 11 12
👆즉, 이 문제는 주어진 배열에서 일단 정수 하나를 고르고, 이 정수와 더했을 때 target이 되는 다른 정수 하나를 배열에서 찾는 문제로 생각할 수 있습니다.
그러면 어떻게 해야 다른 정수 하나를 무식하게 하나씩 비교하지 않고 좀 더 효율적으로 찾을 수 있을까요?
아무 이유도 없이 입력 배열을 오름차순으로 정렬해서 제공하지는 않았겠죠? 😏 빙고! 여기서 이분 탐색(binary search)이 빡! 떠오르신 분들은 축하드리고요! 🥳 아직 이분 탐색에 대해서 잘 모르시는 분들은 관련 설명을 먼저 읽고 돌아오시기를 추천드립니다.
자, 그럼 주어진 예제에 이분 탐색을 한 번 적용해볼까요?
2가 선택된 상태에서, 우측에 있는 4개의 정렬된 수를 대상으로 이분 탐색을 이용해서 7을 찾으면 될 것 같네요.
1 2 [4 6 7 9 10 11 12]
👆검색 구간의 시작 지점을 L(low), 중간 지점을 M(mid), 끝 지점을 H(high)로 가리키겠습니다.
검색 구간의 중앙에 있는 9는 찾으려는 정수 7보다 크므로, 좌측 절반으로 검색 범위를 줄입니다.
4 6 7 9 10 11 12
L M H새 검색 구간의 중앙에 있는 6은 찾으려는 정수 7보다 작으므로, 이번에는 우측 절반으로 검색 범위를 줄입니다.
4 6 7 9 10 11 12
L M H이제 남아있는 정수가 7밖에 없는데, 이 것이 딱 찾으려는 정수네요!
4 6 7 9 10 11 12
L
M
H이렇게 이분 탐색은 원하는 값을 찾을 때 까지 계속해서 검색 구간을 절반씩 줄여나가기 때문에 O(log n)의 성능을 보입니다.
이 알고리즘을 코드로 구현해볼까요?
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
for i in range(len(numbers) - 1):
low, high = i + 1, len(numbers) - 1
while low <= high:
mid = (low + high) // 2
if numbers[i] + numbers[mid] == target:
return [i + 1, mid + 1]
if numbers[i] + numbers[mid] > target:
high = mid - 1
else:
low = mid + 1이 풀이는 for 문 안에서 이분 탐색을 하고 있으므로 시간 복잡도는 O(n) * O(log n), 즉, O(nlog(n)) 입니다.
두 개의 변수 외에는 추가적인 메모리는 사용하고 있지 않으므로 공간 복잡도는 O(1)이 되겠네요.
풀이 3
이분 탐색 외에도 정렬된 데이터를 탐색할 때 자주 사용되는 또 다른 테크닉이 하나 있는데요. 바로 두 개의 포인터를 이용해서 데이터를 찾는 것입니다.
먼저 두 개의 포인터 L(low)와 H(high)를 배열에 양 가장자리에 위치 시킵니다.
그리고 두 개의 포인터에 위치한 정수를 더한 값이 찾으려는 값보다 작으면 더 큰 값이 필요하므로 좌측 포인터 L를 오른쪽으로 한 칸 당깁니다.
반대로 두 개의 포인터에 위치한 정수를 더한 값이 찾으려는 값보다 크면 더 작은 값이 필요하므로 우측 포인터 H를 왼쪽으로 한 칸 당깁니다.
이 작업을 반복하다보면 점점 찾으려는 값으로 두 정수의 합이 수렴을 하게 됩니다.
정말 그런지 동일한 예제에 이 알고리즘을 한 번 적용해보겠습니다.
1 2 4 6 7 9 10 11 12
L H1 + 12 = 13 > 9, 작은 값 필요해서 우측 포인터 왼쪽으로 이동
1 2 4 6 7 9 10 11 12
L H1 + 11 = 12 > 9, 작은 값 필요해서 우측 포인터 왼쪽으로 이동
1 2 4 6 7 9 10 11 12
L H1 + 10 = 11 > 9, 작은 값 필요해서 우측 포인터 왼쪽으로 이동
1 2 4 6 7 9 10 11 12
L H1 + 9 = 10 > 9, 작은 값 필요해서 우측 포인터 왼쪽으로 이동
1 2 4 6 7 9 10 11 12
L H1 + 7 = 8 < 9, 큰 값으 필요해서 좌측 포인터 오른쪽으로 이동
1 2 4 6 7 9 10 11 12
L H2 + 7 = 9, 발견!! 🎉
그럼 이 알고리즘을 코드로 구현해볼까요?
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
low, high = 0, len(numbers) - 1
while low < high:
total = numbers[low] + numbers[high]
if total < target:
low += 1
elif total > target:
high -= 1
else:
return [low + 1 , high + 1]이 풀이는 while 문 하나만 사용하므로 시간 복잡도가 O(n)이며 공간 복잡도는 O(1)입니다.
마치면서
Two Sum 문제와 얼핏 비슷하다고 생각할 수 있지만 입력 데이터가 정렬되었다는 사실 하나만으로 상당히 다르게 접근할 수 있는 문제였습니다.