LeetCode

LeetCode 167 Two Sum II 풀이: 정렬 배열 양끝 투 포인터

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

플랫폼의 Medium 등급과는 별개로, 이 글에서는 Level 2로 판단했다. 배열이 정렬되어 있다는 조건에서 양끝 포인터를 움직이는 규칙을 스스로 찾아야 하므로 단순 반복문 문제인 Level 1보다는 어렵다. 다만 포인터 두 개와 합 비교만 사용하고, 재귀·복잡한 상태 관리나 특수한 자료구조가 필요하지 않아 Level 3까지의 난이도는 아니다. 1-based 인덱스 반환과 포인터를 안전하게 버릴 수 있는 이유를 설명해야 하는 점을 포함해 Level 2로 평가했다.

1. 문제 요약

오름차순으로 정렬된 1-based 정수 배열 numbers와 target이 주어진다. 서로 다른 두 원소의 합이 target이 되는 인덱스 [index1, index2]를 반환한다.

중요한 조건은 다음과 같다.

  • 배열 길이는 2 이상 3 * 10^4 이하다.
  • 배열은 비내림차순으로 정렬되어 있다.
  • 정답은 정확히 하나 존재한다.
  • 같은 원소를 두 번 사용할 수 없다.
  • 반환 인덱스는 0-based가 아니라 1-based다.
  • 추가 공간은 상수 공간만 사용할 수 있다.

numbers = [2,7,11,15], target = 9이면 2 + 7 = 9이므로 [1,2]를 반환한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

구간 판정과 포인터 이동

left는 배열의 첫 인덱스, right는 마지막 인덱스에서 시작한다. 두 값의 합을 current_sum이라고 할 때 정렬 조건에 따라 다음과 같이 이동한다.

  • current_sum < target: 합을 키워야 하므로 더 큰 값을 가리키도록 left += 1
  • current_sum > target: 합을 줄여야 하므로 더 작은 값을 가리키도록 right -= 1
  • current_sum == target: 정답을 찾았으므로 1-based 인덱스를 반환

합의 대소가 버릴 포인터를 결정하는 이유

현재 numbers[left] + numbers[right]가 target보다 작다고 하자. left를 그대로 두고 right를 더 왼쪽으로 옮기면 두 번째 값이 더 작아지므로 합은 지금보다 더 작아진다. 현재 left로는 어떤 더 오른쪽 원소와도 정답을 만들 수 없다. left를 증가시켜 더 큰 값을 시도해도 정답을 놓치지 않는다.

반대로 합이 target보다 크면 right를 그대로 두고 left를 오른쪽으로 이동할수록 합이 더 커지므로 정답이 될 수 없다. 이때는 right를 감소시켜야 한다.

이처럼 한 번 제외한 포인터 위치는 정답 후보가 될 수 없다는 근거가 있으므로, 모든 쌍을 확인하지 않고 한 번의 선형 이동으로 탐색할 수 있다.

상태 전이와 인덱스 처리

Python 리스트는 0-based 인덱스를 사용하지만 문제의 반환 형식은 1-based다. numbers[left]와 numbers[right]를 찾은 뒤 반환할 때 각각 1을 더해야 한다.

포인터가 만날 때까지 반복한다. 문제 조건상 정답이 반드시 존재하므로 정상 입력에서는 두 포인터가 만나기 전에 반환하지만, 반복문 뒤의 반환값을 두어 함수 반환 형식을 완성한다.

오답 접근과 반례

모든 두 원소 조합을 확인하는 완전탐색은 정답을 찾을 수 있지만 O(n^2) 시간이 필요하다. 배열 길이가 3 * 10^4까지 가능하므로 모든 쌍을 검사하는 방식은 비효율적이다.

numbers = [1,2,3,...,30000]
target = 59999

정렬되어 있는데도 해시 맵을 사용해 보완값을 저장하는 방식은 평균 O(n) 시간에 풀 수 있지만 O(n) 추가 공간을 사용한다. 이 문제는 상수 공간 조건이 있으므로 투 포인터가 조건에 더 잘 맞는다.

반환 인덱스에 1을 더하지 않으면 값은 맞아도 출력 형식이 틀린다.

시간·공간 복잡도

각 반복에서 left 또는 right 중 하나가 한 칸씩 이동하고, 두 포인터는 배열을 최대 한 번 통과한다. 시간 복잡도는 O(n)이고, 포인터 몇 개만 사용하므로 공간 복잡도는 O(1)다.

3. 문제 해결 코드 (Python)

양끝 값을 더해 target과 비교하고, 합이 작은지 큰지에 따라 포인터를 이동한다. 정답을 반환할 때 문제의 1-based 인덱스 형식에 맞춰 +1을 적용한다.

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        left = 0
        right = len(numbers) - 1

        while left < right:
            current_sum = numbers[left] + numbers[right]

            if current_sum == target:
                return [left + 1, right + 1]
            if current_sum < target:
                left += 1
            else:
                right -= 1

        return []

정답이 없는 경우를 대비해 반복문 뒤에 빈 리스트를 반환하지만, 문제 조건에서는 항상 정답이 하나 존재한다. 같은 값이 여러 번 있어도 서로 다른 인덱스의 원소라면 정상적인 후보로 처리된다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 1-based 인덱스와 음수 경계를 확인할 수 있다.

solver = Solution()
assert solver.twoSum([2, 7, 11, 15], 9) == [1, 2]
assert solver.twoSum([2, 3, 4], 6) == [1, 3]
assert solver.twoSum([-1, 0], -1) == [1, 2]

4. 공식 예제와 추가 검증

작성한 twoSum 함수를 Python으로 실행해 공식 예제와 중복 값·음수·양끝 경계를 확인했다.

공식 예제

입력 기대 출력 확인 결과
numbers=[2,7,11,15], target=9 [1,2] 통과
numbers=[2,3,4], target=6 [1,3] 통과
numbers=[-1,0], target=-1 [1,2] 통과

추가 검증 1: 같은 값 두 개

입력: numbers = [1,1,3,4], target = 2
기대 출력: [1,2]
확인 결과: 통과
검증 목적: 같은 값이 서로 다른 인덱스에 있을 때 정답으로 처리하는지 확인

추가 검증 2: 음수와 0

입력: numbers = [-5,-2,0,3,8], target = 1
기대 출력: [2,4]
확인 결과: 통과
검증 목적: 음수와 0이 포함된 정렬 배열에서 포인터 이동을 확인

추가 검증 3: 양끝 원소가 정답

입력: numbers = [-10,-3,0,4,12], target = 2
기대 출력: [1,5]
확인 결과: 통과
검증 목적: 초기 양끝 포인터가 바로 정답인 경우 확인

5. 다른 풀이 방식 검색 및 비교

해시 맵에 각 값을 저장하고 target - number를 조회하면 정렬 여부와 관계없이 평균 O(n) 시간에 풀 수 있다. 하지만 모든 값을 저장하므로 O(n) 공간이 필요하다.

정렬된 배열에서는 합의 크기에 따라 포인터를 안전하게 버릴 수 있으므로 추가 공간 없이 O(n) 시간에 해결하는 투 포인터 방식이 더 적합하다. 이 문제에서는 이미 정렬된 입력과 상수 공간 조건이 주어졌기 때문에 투 포인터를 선택했다.

마무리

Two Sum II는 정렬된 배열에서 양끝 두 값의 합을 비교해 탐색 범위를 줄이는 투 포인터 문제다. 합이 작으면 왼쪽을 오른쪽으로, 합이 크면 오른쪽을 왼쪽으로 이동하면 정답 후보를 안전하게 제외할 수 있다. 1-based 인덱스 반환만 주의하면 O(n) 시간과 O(1) 공간으로 해결할 수 있다.

관련 문제

#투 포인터#LeetCode#난이도 2