파이썬으로 리스트에서 합이 K가 되는 두 숫자 찾기

문제 개요

숫자로 이루어진 리스트 nums와 하나의 숫자 k가 주어졌을 때, 리스트 안에서 서로 다른 두 숫자를 골라 그 합이 정확히 k가 되는 경우가 존재하는지 확인하는 프로그램을 만들어 보겠습니다.

여기에는 몇 가지 조건이 붙습니다. 첫째, 같은 요소를 두 번 사용할 수 없습니다. 둘째, 리스트의 숫자는 음수나 0을 포함할 수 있습니다.

예를 들어 입력이 nums = [45, 18, 9, 13, 12], k = 31이라면, 18 + 13 = 31이 성립하므로 결과는 True가 됩니다.

해결 접근 방식: 해시 셋(Set) 활용

모든 숫자 쌍을 일일이 비교하는 브루트 포스 방식은 O(n²)의 시간이 걸려 비효율적입니다. 대신 해시 셋을 이용하면 단 한 번의 순회(O(n))만으로 문제를 해결할 수 있습니다.

핵심 아이디어는 간단합니다. 각 숫자 num을 확인할 때, 그 숫자와 더했을 때 k가 되는 값인 k - num(보완값)을 미리 셋에 저장해 두는 것입니다. 이후 순회 중 현재 숫자가 이미 셋에 존재한다면, 그것은 앞서 등장한 어떤 숫자의 보완값과 일치한다는 의미이므로 합이 k가 되는 두 숫자가 존재하는 것입니다.

알고리즘 단계

temp_set: 새로운 빈 집합을 생성합니다.
리스트 nums의 각 숫자 num에 대해 반복합니다.
- num이 이미 temp_set에 있다면 True를 반환합니다.
- 그렇지 않으면 k - num 값을 temp_set에 추가합니다.
반복이 끝날 때까지 조건을 만족하지 못하면 False를 반환합니다.

구현 예제

class Solution:
    def solve(self, nums, k):
        temp_set = set()
        for num in nums:
            if num in temp_set:
                return True
            temp_set.add(k - num)
        return False

ob = Solution()
nums = [45, 18, 9, 13, 12]
k = 31
print(ob.solve(nums, k))

입력

[45, 18, 9, 13, 12], 31

출력

True

코드 동작 과정 살펴보기

위 예제가 실제로 어떻게 진행되는지 단계별로 추적해 보겠습니다.

num = 45: 셋에 없음 → 31 − 45 = −14를 셋에 추가 → {−14}
num = 18: 셋에 없음 → 31 − 18 = 13을 셋에 추가 → {−14, 13}
num = 9: 셋에 없음 → 31 − 9 = 22를 셋에 추가 → {−14, 13, 22}
num = 13: 셋에 13이 이미 존재! → True 반환

13은 앞서 18의 보완값으로 저장된 숫자입니다. 따라서 18 + 13 = 31이라는 답을 찾게 됩니다.

시간 및 공간 복잡도

시간 복잡도: O(n) — 리스트를 한 번만 순회하며, 셋의 조회와 삽입은 평균적으로 O(1)입니다.
공간 복잡도: O(n) — 최악의 경우 모든 숫자의 보완값을 셋에 저장해야 할 수 있습니다.

파이썬으로 리스트에서 합이 K가 되는 두 숫자 찾기 — 해시 셋 활용 O(n) 풀이