문제 개요
오름차순으로 정렬된 숫자 리스트 nums와 값 k가 주어졌다고 가정해 보겠습니다. 이때 리스트에서 임의로 선택한 두 요소의 합이 정확히 k가 되는지 확인해야 합니다. 단, 숫자에는 음수나 0도 포함될 수 있으며, 추가 메모리를 거의 사용하지 않는 상수 공간(O(1)) 안에서 문제를 해결해야 한다는 조건이 있습니다.
예를 들어, 입력이 nums = [-8, -3, 2, 7, 9], k = 4라면 결과는 True입니다. 그 이유는 7과 -3을 선택했을 때 7 + (-3) = 4로 k와 같아지기 때문입니다.
해결 접근 방법: 투 포인터(Two Pointer)
정렬된 리스트라는 특성을 활용하면 투 포인터(Two Pointer) 기법으로 효율적으로 문제를 해결할 수 있습니다. 이 방식은 리스트 양 끝에 포인터를 배치하고, 합의 크기를 비교하며 포인터를 안쪽으로 이동시키는 원리로 동작합니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)로 조건을 모두 만족합니다.
해결 절차는 다음과 같습니다.
- i := 0 (리스트의 시작 인덱스)
- j := 리스트 길이 - 1 (리스트의 마지막 인덱스)
- i < j인 동안 아래 과정을 반복
- cur_sum := nums[i] + nums[j]
- cur_sum == k이면 True 반환
- cur_sum < k이면 i := i + 1 (합을 키우기 위해 왼쪽 포인터 이동)
- 그 외의 경우 j := j - 1 (합을 줄이기 위해 오른쪽 포인터 이동)
- 반복이 끝나면 False 반환
구현 예제
다음 구현 예제를 통해 동작 방식을 더 쉽게 이해할 수 있습니다.
def solve(nums, k):
i = 0
j = len(nums) - 1
while i < j:
cur_sum = nums[i] + nums[j]
if cur_sum == k:
return True
elif cur_sum < k:
i += 1
else:
j -= 1
return False
nums = [-8, -3, 2, 7, 9]
k = 4
print(solve(nums, k))입력
[-8, -3, 2, 7, 9], 4
출력
True
동작 원리 정리
처음에는 가장 작은 값(-8)과 가장 큰 값(9)의 합인 1을 계산하고, 이것이 k(4)보다 작으므로 왼쪽 포인터를 한 칸 이동합니다. 다음으로 -3과 9의 합인 6을 계산하면 k보다 크므로 이번에는 오른쪽 포인터를 이동합니다. 이후 -3과 7의 합이 4로 k와 일치하므로 True가 반환됩니다. 이처럼 매 단계마다 합이 k보다 작으면 왼쪽 포인터를, 크면 오른쪽 포인터를 이동시키면서 답을 찾거나 두 포인터가 교차할 때까지 탐색을 진행합니다.