숫자로 이루어진 리스트 nums와 하나의 값 k가 주어졌을 때, 리스트에서 서로 다른 세 개의 요소 (a, b, c)를 선택하여 |a + b + c − k|의 값을 최소화하고, 그 절대 차이를 반환하는 문제를 생각해 봅시다.
예를 들어 입력이 nums = [2, 5, 25, 6], k = 14라고 한다면, 출력은 1이 됩니다. [2, 5, 6]을 선택하면 합이 13이 되어 14에 가장 가깝고, 절대 차이는 |13 − 14| = 1이기 때문입니다.
문제 해결 접근 방법
이 문제는 정렬과 투 포인터(Two Pointer) 기법을 활용하면 효율적으로 해결할 수 있습니다. 전체 과정은 다음과 같습니다.
- 리스트 nums를 오름차순으로 정렬합니다.
- ans를 충분히 큰 값(10의 9제곱)으로 초기화합니다.
- i를 0부터 리스트 크기까지 반복하면서 다음을 수행합니다.
- j := i + 1, k := 리스트 크기 − 1로 설정합니다.
- j < k인 동안 아래를 반복합니다.
- s := nums[i] + nums[j] + nums[k]를 계산합니다.
- s가 target 이하라면, ans를 ans와 target − s 중 작은 값으로 갱신하고 j를 1 증가시킵니다.
- 그렇지 않다면, ans를 ans와 s − target 중 작은 값으로 갱신하고 k를 1 감소시킵니다.
- 최종적으로 ans를 반환합니다.
구현 예제
아래 파이썬 코드를 통해 실제 구현 방법을 확인해 보겠습니다.
class Solution: def solve(self, nums, target): nums.sort() ans = 1e9 for i in range(len(nums)): j = i + 1 k = len(nums) - 1 while j < k: s = nums[i] + nums[j] + nums[k] if s <= target: ans = min(ans, target - s) j += 1 else: ans = min(ans, s - target) k -= 1 return ans ob1 = Solution() nums = [2, 5, 25, 6] k = 14 print(ob1.solve(nums, k))
입력
[2, 5, 25, 6], 14
출력
1
알고리즘 동작 원리
이 알고리즘이 효율적인 이유는 정렬된 배열에서 두 포인터를 활용해 불필요한 탐색을 제거하기 때문입니다. 현재 세 수의 합이 target보다 작으면 더 큰 값을 만들기 위해 왼쪽 포인터(j)를 이동시키고, 합이 target보다 크면 더 작은 값을 만들기 위해 오른쪽 포인터(k)를 이동시킵니다. 이렇게 하면 모든 조합을 확인하는 O(n³) 브루트포스 방식 대신 O(n²)의 시간 복잡도로 문제를 해결할 수 있습니다.