[PS] LeetCode: Two Sum II - Input Array Is Sorted

오늘은 LeetCode의 Two Sum II - Input Array Is Sorted 문제를 풀어보겠습니다.

 

1. 문제

오름차순으로 정렬된 `numbers`라는 정수 배열이 주어졌습니다. (인덱스 1부터 시작) 더해서 `target` 숫자가 되는 두 숫자를 찾아 인덱스를 반환해주세요. 답을 만족하는 케이스는 한 가지밖에 없고, 같은 원소를 두 번 사용하면 안됩니다.

 

2. 예제

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]

Input: numbers = [2, 3, 4], target = 6
Output: [1,3]

 

3. 접근 방법

3.1. 브루트 포스

가장 단순한 방법은 배열에 있는 숫자 두 개로 만들 수 있는 모든 숫자 조합을 찾은 뒤, 이 숫자들이 조건을 만족하는지 확인하는 것입니다. 아래와 같은 방식으로 구현해볼 수 있습니다. 이 방법은 배열의 모든 숫자를 제곱만큼 탐색해야 하기 때문에 비효율적인 방법이라고 할 수 있습니다.

 

3.2. 투 포인터

좀 더 효율적인 방법은 없을까요? 배열이 오름차순으로 정렬되어 있다는 특성을 활용할 수 있습니다. 양 끝에서부터 포인터를 잡아 target과 비교하고, 작으면 오른쪽 포인터를 하나 왼쪽으로 이동시키고, 반대의 경우라면 왼쪽 포인터를 오른쪽으로 이동시킵니다. 배열의 요소만큼 반환하면 결국 답을 찾아낼 수 있습니다. 

 

4. 알고리즘 분석

4.1. 시간 복잡도: O(n)

최종 답안은 최대 입력 배열의 길이만큼만 순회를 하면 됩니다. 브루트 포스 대비 O(n^2) 더 효율적이라고 할 수 있습니다.

 

4.2. 공간 복잡도: O(1)

최종 답안의 공간 복잡도는 입력 배열의 길이와는 무관합니다. 입력 크기에 상관없이 메모리 사용량이 일정하므로 공간 복잡도는 O(1)입니다.

 

5. 나가며

투 포인터가 서로 다른 방향으로 이동하면서 탐색을 하는 문제였습니다. 다음에는 또 다른 문제들을 풀어보겠습니다.