숫자 리스트 nums와 값 k가 주어졌을 때, 리스트에서 서로 다른 위치의 네 개 요소를 골라 그 합이 정확히 k가 되도록 할 수 있는지 확인하는 문제입니다.
예를 들어 입력이 nums = [11, 4, 6, 10, 5, 1], k = 25라면, [4, 6, 10, 5]의 합이 25이므로 출력은 True가 됩니다.
해결 접근 방법
이 문제는 정렬과 투 포인터(Two Pointers) 기법을 활용하면 효율적으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- 리스트 nums를 오름차순으로 정렬합니다.
- n := 리스트의 크기로 설정합니다.
- i를 0부터 n - 4까지 반복합니다.
- j를 i + 1부터 n - 3까지 반복합니다.
- 왼쪽 포인터 l := j + 1, 오른쪽 포인터 h := n - 1로 초기화합니다.
- l < h인 동안 다음을 반복합니다.
- summ := nums[i] + nums[j] + nums[l] + nums[h]를 계산합니다.
- summ이 k와 같으면 True를 반환합니다.
- summ이 k보다 작으면 l을 1 증가시켜 합을 키웁니다.
- 그렇지 않으면(합이 k보다 크면) h를 1 감소시켜 합을 줄입니다.
- 모든 경우를 확인한 후에도 찾지 못하면 False를 반환합니다.
구현 예제
class Solution: def solve(self, nums, k): nums.sort() n = len(nums) for i in range(n - 3): for j in range(i + 1, n - 2): l, h = j + 1, len(nums) - 1 while l < h: summ = nums[i] + nums[j] + nums[l] + nums[h] if summ == k: return True elif summ < k: l += 1 else: h -= 1 return False ob1 = Solution() nums = [11, 4, 6, 10, 5, 1] k = 25 print(ob1.solve(nums, k))
입력
[11, 4, 6, 10, 5, 1], 25
출력
True
시간 복잡도 분석
리스트를 먼저 정렬하는 데 O(n log n)이 소요되고, 이후 두 개의 고정 인덱스(i, j)에 대해 투 포인터 탐색을 수행하므로 전체 시간 복잡도는 O(n³)입니다. 단순히 네 개의 요소를 모두 조합해 확인하는 브루트 포스 방식(O(n⁴))보다 효율적이며, 추가 공간 복잡도는 O(1)로 제자리 정렬만 사용하기 때문에 메모리 측면에서도 유리합니다.