Two Sum II: Sorted Input
비내림차순으로 정렬된 정수 배열 numbers와 정수 target이 주어집니다. 서로 다른 위치에 있는 두 값의 합이 target이 되는 쌍은 정확히 하나입니다. 이 두 위치를 0부터 시작하는 인덱스로 반환하되, 더 작은 인덱스를 먼저 반환하세요.
함수
- numbersinteger-array
- 정렬된 정수 배열
- targetinteger
- 두 값의 합이 도달해야 하는 값
- 반환값integer-array
- i < j이고 numbers[i] + numbers[j] == target인 0부터 시작하는 두 인덱스 [i, j]
제약 조건
2 ≤ numbers.length ≤ 104-5 × 108 ≤ numbers[i] ≤ 5 × 108-109 ≤ target ≤ 109numbers는 감소하지 않는 순서로 정렬되어 있습니다.- 인덱스 쌍은 정확히 하나이며,
i < j이고numbers[i] + numbers[j] == target을 만족합니다.
예제
- 입력
- numbers = [-4, 1, 3, 8, 12]target = 9
- 출력
- [1, 3]
- 설명
- 1은 인덱스 1에 있고 8은 인덱스 3에 있으며, 1 + 8 = 9입니다. 다른 어떤 쌍도 9가 되지 않습니다. 예를 들어, -4 + 12 = 8입니다.
- 입력
- numbers = [2, 2, 5, 7]target = 4
- 출력
- [0, 1]
- 설명
- 인덱스 0과 1에 있는 두 개의 2는 서로 다른 위치이므로 쌍을 이룰 수 있습니다: 2 + 2 = 4.
- 입력
- numbers = [-10, -3, 0, 6]target = -4
- 출력
- [0, 3]
- 설명
- 인덱스 0의 -10과 인덱스 3의 6을 더하면 -10 + 6 = -4입니다. 답은 배열 전체에 걸쳐 있을 수 있습니다.
제출 시 숨은 테스트 +13개
후속 질문
추가 메모리를 O(1)만 사용하면서 O(n) 시간 안에 해결할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
배열은 정렬되어 있습니다. 가장 작은 값과 가장 큰 값을 함께 살펴보세요. 두 값의 합이
target보다 작으면 무엇을 알 수 있을까요?첫 번째 값과 마지막 값을 더한 값이 너무 작다면, 마지막 값이 이미 가장 크기 때문에 첫 번째 값은 어떤 짝과 더해도 너무 작습니다. 따라서 첫 번째 값을 제외할 수 있습니다.
각 끝에 포인터를 하나씩 둡니다. 합이 너무 작으면 왼쪽 포인터를 오른쪽으로 이동하고, 합이 너무 크면 오른쪽 포인터를 왼쪽으로 이동합니다. 합이
target과 같아지면 멈춥니다.
풀이
해시 맵은 정렬되지 않은 버전을 한 번의 순회로 해결하지만, O(n)의 메모리가 필요합니다. 여기서는 배열이 정렬되어 있고, 그 순서에 따라 어느 방향으로 이동할지 알 수 있습니다. 양 끝에 포인터를 하나씩 놓으세요. 합이 너무 작으면 왼쪽 값이 더 커져야 도움이 되고, 합이 너무 크면 오른쪽 값이 더 작아져야 도움이 됩니다. 각 단계에서 값 하나를 확실히 제외하므로, 추가 메모리 없이 한 번의 순회로 쌍을 찾을 수 있습니다.
모든 쌍을 확인하세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
모든 위치 쌍 i < j을 확인하고 numbers[i] + numbers[j]가 target과 같은지 테스트하세요. i는 왼쪽에서 시작하고 j는 그 바로 다음 위치에서 시작하므로, 처음 찾은 쌍은 이미 인덱스가 작은 값이 먼저 옵니다.
이 방법은 올바르지만 정렬된 순서를 활용하지 않습니다. n = 10^4이면 쌍이 약 5 × 10^7개이고, 답이 배열의 끝부분에 있으면 거의 모든 쌍을 테스트하게 됩니다. 이는 큰 테스트에서는 너무 느립니다.
알고리즘
- 모든 인덱스에 대해
i를 반복합니다. i+1부터 마지막 인덱스까지j를 반복합니다.numbers[i] + numbers[j]가target과 같으면[i, j]를 반환합니다.
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i, j]
return []각 파트너에 대한 이진 탐색
핵심 아이디어
첫 번째 값 numbers[i]를 고정하면 그 짝이 무엇인지 정확히 알 수 있습니다. 바로 target - numbers[i]입니다. i의 오른쪽에 있는 배열 부분은 정렬되어 있으므로, 이진 검색을 사용하면 짝이 있는지 O(log n) 단계 만에 확인할 수 있습니다.
[-4, 1, 3, 8, 12]와 target = 9의 경우: i = 0일 때 짝은 13이지만, 없습니다. i = 1일 때 짝은 8이며, 검색을 통해 인덱스 3에서 찾습니다. 답은 [1, 3]입니다.
i의 오른쪽만 검색하면 더 작은 인덱스가 앞에 오고, 값이 자기 자신과 짝을 이루는 것을 방지할 수 있습니다. 짝은 하나뿐이므로, 해당 범위에 짝 값은 최대 한 번만 나타나며 일치하는 값이 있으면 그것이 답입니다. 전체적으로 O(log n) 검색을 n번 수행합니다.
알고리즘
i를 0부터n-2까지 반복합니다.need = target - numbers[i]를 계산합니다.- 인덱스
i+1부터n-1까지에서need를 이진 검색합니다. mid에서 찾으면[i, mid]를 반환합니다.
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n - 1):
need = target - numbers[i]
lo, hi = i + 1, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if numbers[mid] == need:
return [i, mid]
if numbers[mid] < need:
lo = mid + 1
else:
hi = mid - 1
return []양쪽 끝에서 시작하는 두 포인터
핵심 아이디어
left = 0과 right = n-1에서 시작해 numbers[left] + numbers[right]를 살펴보세요. 이 값이 target과 같으면 끝입니다. 값이 너무 작다면 numbers[left]는 답에 포함될 수 없습니다. 아직 고려 중인 가장 큰 값과 짝을 이루어도 합이 목표에 미치지 못하기 때문입니다. 따라서 left를 오른쪽으로 옮기세요. 합이 너무 크다면 numbers[right]도 답에 포함될 수 없습니다. 남은 값 중 가장 작은 값과 짝을 이루어도 합이 목표를 초과하기 때문입니다. 따라서 right를 왼쪽으로 옮기세요.
이동할 때마다 쌍에 절대 포함될 수 없는 값 하나를 제외하며, 정답 쌍 자체는 제외되지 않습니다. 포인터는 최대 n-1번 이동한 뒤 만납니다. 따라서 탐색은 O(n)이고 변수 두 개를 사용합니다.
[-4, 1, 3, 8, 12]에서 target = 9인 경우: -4 + 12 = 8은 너무 작으므로 left를 인덱스 1로 옮깁니다. 그런 다음 1 + 12 = 13은 너무 크므로 right를 인덱스 3으로 옮깁니다. 이제 1 + 8 = 9이므로 답은 [1, 3]입니다.
알고리즘
left를 0으로 설정하고right를n-1로 설정합니다.left < right인 동안total = numbers[left] + numbers[right]를 계산합니다.total이target과 같으면[left, right]를 반환합니다.total이 더 작으면left에 1을 더하고, 더 크면right에서 1을 뺍니다.
def twoSumSorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return []
함정과 경계 사례
두 포인터 루프는 짧기 때문에, 주변의 세부 사항에 버그가 숨어 있습니다.
- 1부터 시작하는 위치를 반환하는 경우. 이 버전에서는 0부터 시작하는 인덱스를 사용합니다.
[-4, 1, 3, 8, 12]와target = 9의 경우 답은[2, 4]가 아니라[1, 3]입니다. Lua와 R에서는 반환하기 전에 1을 빼세요. left <= right로 반복하는 경우. 포인터가 만났을 때 합을 계산하면 같은 값을 두 번 사용하게 됩니다.- 잘못된 포인터를 이동하는 경우. 합이 너무 작으면 더 큰 값이 필요하며, 그런 값을 제공할 수 있는 것은
left뿐입니다. - 중복 값을 거부하는 경우.
target = 4일 때[2, 2, 5, 7]에서는 서로 다른 위치에 있는 2 두 개를 사용합니다. - 오버플로. 여기의 제한에서는 모든 합이 32비트 정수 범위 안에 있습니다. 값이
10^9까지 가능하다면 64비트 형식으로 더하세요.
자주 묻는 질문4
정렬된 배열에서 Two Sum을 풀 때 투 포인터가 작동하는 이유는 무엇인가요?
양쪽 끝의 합이 너무 작으면, 오른쪽 끝이 아직 후보인 값 중 가장 크므로 왼쪽 값은 남은 모든 짝과 비교해도 너무 작습니다. 왼쪽 값을 완전히 제외해도 됩니다. 같은 논리로 합이 너무 크면 오른쪽 값을 제외합니다. 정답 쌍은 절대 제외되지 않으므로 포인터는 그 쌍에서 멈춥니다.
Two Sum II의 시간 복잡도는 얼마인가요?
두 포인터 풀이의 시간 복잡도는 O(n)이고 추가 공간 복잡도는 O(1)입니다. 각 단계에서 포인터 하나를 안쪽으로 이동하며, 최대 n-1단계 후 두 포인터가 만납니다. 각 대응 항목을 이진 탐색하면 O(n log n)이 걸리고, 모든 쌍을 확인하면 O(n²)이 걸립니다.
첫 번째 Two Sum에서처럼 해시 맵을 사용하지 않는 이유는 무엇인가요?
해시 맵도 작동하며 시간 복잡도는 O(n)이지만, 최대 n개의 값을 저장합니다. 정렬된 순서에서는 합만으로 두 포인터가 어느 쪽으로 이동해야 하는지 알 수 있으므로 그 메모리는 필요하지 않습니다. 면접관은 주어진 순서를 활용하는지 확인하기 위해 이 문제를 냅니다.
여기서는 이진 검색이 언제 더 나은 선택인가요?
한 값이 고정되어 있고 짝이 되는 값만 찾으면 되는 경우입니다. numbers[0]이 쌍에 반드시 포함되어야 한다면, 이진 탐색 한 번으로 다른 인덱스를 O(log n)에 찾을 수 있습니다. 어떤 쌍인지 모르는 경우에는 두 포인터를 이용한 탐색이 n번의 개별 탐색보다 빠릅니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def twoSumSorted(numbers, target):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
numbers = [-4, 1, 3, 8, 12] target = 9
기대값
[1, 3]