파이썬으로 합이 k가 되는 서로 다른 세 요소가 존재하는지 확인하는 프로그램

문제 소개

숫자로 이루어진 리스트 nums와 목표값 k가 주어졌을 때, 리스트 안에서 서로 다른 세 요소를 골라 그 합이 정확히 k가 되도록 할 수 있는지 확인하는 것이 이번 문제의 목표입니다.

예를 들어 입력이 nums = [11, 4, 6, 10, 5, 1], k = 20이라면 결과는 True입니다. 리스트 속 [4, 6, 10] 세 숫자의 합이 정확히 20이기 때문입니다.

해결 접근 방법

이 문제는 리스트를 먼저 정렬한 뒤 투 포인터(two pointer) 기법을 적용하면 효율적으로 해결할 수 있습니다. 동작 순서를 단계별로 정리하면 다음과 같습니다.

1. 리스트 nums를 오름차순으로 정렬합니다.
2. 두 포인터를 초기화합니다. 왼쪽 포인터 l := 0, 오른쪽 포인터 r := len(nums) - 1.
3. l < r - 1이 유지되는 동안 아래 과정을 반복합니다.
   • 필요한 세 번째 값을 계산합니다. t := k - nums[l] - nums[r]
   • 만약 nums[r - 1] < t라면 현재 구간에서는 t를 만들 수 없으므로 l을 1 증가시키고 다음 반복으로 넘어갑니다.
   • m을 l + 1부터 r - 1까지 하나씩 이동하며 검사합니다.
     • nums[m] > t이면 더 작은 합이 필요하다는 의미이므로 r을 1 감소시키고 내부 반복문을 빠져나옵니다.
     • nums[m] == t이면 조건을 충족하는 세 요소를 찾은 것이므로 즉시 True를 반환합니다.
4. 끝까지 확인했는데도 성공하지 못했다면 False를 반환합니다.

여기서 m은 항상 l과 r 사이에 위치하므로 선택되는 세 인덱스는 서로 겹치지 않습니다. 즉, 중복 없는 세 개의 요소를 사용해야 한다는 조건이 자연스럽게 보장됩니다.

구현 예시

아래 파이썬 코드를 통해 실제 동작을 더 명확하게 이해할 수 있습니다.

class Solution:
    def solve(self, nums, k):
        nums.sort()
        l, r = 0, len(nums) - 1
        while l < r - 1:
            t = k - nums[l] - nums[r]
            if nums[r - 1] < t:
                l += 1
                continue
            for m in range(l + 1, r):
                if nums[m] > t:
                    r -= 1
                    break
                if nums[m] == t:
                    return True
        return False

ob1 = Solution()
nums = [11, 4, 6, 10, 5, 1]
k = 20
print(ob1.solve(nums, k))

입력

[11, 4, 6, 10, 5, 1], 20

출력

True

시간 복잡도

정렬에는 O(n log n), 이후 포인터 탐색에는 최악의 경우 O(n²)의 시간이 걸리므로 전체 시간 복잡도는 O(n²)입니다. 포인터 변수 외에 추가 메모리가 거의 필요하지 않아 공간 복잡도는 O(1) 수준으로 매우 효율적입니다.