코딩 테스트에서 가장 자주 출제되는 대표적인 알고리즘 문제 중 하나인 Two Sum(두 수의 합)을 파이썬으로 해결하는 방법을 알아보겠습니다.
문제 설명
정수로 이루어진 배열이 하나 주어집니다. 이 배열에서 두 요소를 골라 더했을 때 주어진 목표값(target)과 일치하도록 만드는 두 요소의 인덱스를 반환해야 합니다.
여기에는 한 가지 전제 조건이 있습니다. 바로 항상 유일한 해가 하나만 존재한다는 것입니다. 즉, 동일한 목표값에 대해 두 개 이상의 서로 다른 인덱스 쌍이 존재하는 경우는 없다고 가정합니다.
예시
배열이 A = [2, 8, 12, 15]이고 목표 합계가 20이라고 가정해 보겠습니다. 이때 A[1] + A[2] = 8 + 12 = 20이므로, 결과로 인덱스 1과 2를 반환하면 됩니다.
해결 접근 방식
모든 요소 쌍을 일일이 비교하는 브루트 포스 방식은 O(n²)의 시간 복잡도를 가져 비효율적입니다. 대신 해시맵(파이썬 딕셔너리)을 활용하면 O(n) 시간 안에 문제를 해결할 수 있습니다.
핵심 아이디어는 간단합니다. 배열을 순회하면서 현재 요소 nums[i]에 대해 '목표값에서 현재 요소를 뺀 값(target − nums[i])', 즉 필요한 짝꿍 숫자를 이전에 이미 만났는지 딕셔너리에서 확인하는 것입니다.
- 저장소로 사용할 빈 딕셔너리(required)를 생성합니다.
- 인덱스 i를 0부터 n−1까지 반복합니다(n은 배열의 길이).
- 만약 target − nums[i]가 딕셔너리에 이미 존재한다면, 저장되어 있던 해당 인덱스와 현재 인덱스 i를 함께 반환합니다.
- 존재하지 않는다면 현재 값을 키로, 인덱스를 값으로 하여 딕셔너리에 추가합니다(required[nums[i]] = i).
파이썬 구현 코드
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
required = {}
for i in range(len(nums)):
if target - nums[i] in required:
return [required[target - nums[i]], i]
else:
required[nums[i]] = i
input_list = [2, 8, 12, 15]
ob1 = Solution()
print(ob1.twoSum(input_list, 20))입력
input_list = [2, 8, 12, 15]
target = 20출력
[1, 2]시간 복잡도 분석
이 알고리즘은 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 또한 최악의 경우 모든 요소를 딕셔너리에 저장하게 되므로 공간 복잡도 역시 O(n)입니다. 이중 반복문을 사용하는 단순 탐색 방식(O(n²))에 비해 훨씬 효율적이며, 실제 코딩 테스트에서 권장되는 표준적인 풀이 방법입니다.