LeetCode 1 - Two Sum · codetosoul

배열에서 두 값을 골라 target을 만드는 문제다. 난이도는 Easy지만, brute force로 모든 조합을 확인하는 방식과 hash map으로 필요한 값을 찾는 방식을 비교하기 좋다.

문제 링크 & 설명

문제 링크: 1. Two Sum
요약: 정수 배열 nums와 정수 target이 주어졌을 때, 서로 다른 두 원소의 합이 target이 되는 인덱스 두 개를 반환하는 문제다.

예를 들어 입력이 이렇게 주어진다고 해보자.

nums = [2, 7, 11, 15]
target = 9

2와 7을 더하면 9가 되므로 결과는 [0, 1]이다. 같은 원소를 두 번 사용할 수는 없고, 문제에서는 정답이 정확히 하나 존재한다고 가정한다.

처음에는 모든 조합을 확인하는 방식이 가장 바로 떠오른다. 두 수의 합을 확인해야 하므로, 한 원소를 고르고 그 뒤의 원소들을 차례대로 비교하면 답을 찾을 수 있다. 다만 이 방식은 입력이 커질수록 같은 형태의 비교가 많이 반복되고, 그 반복을 줄이려면 “지금 필요한 다른 값이 이미 있었는지”를 빠르게 확인할 방법이 필요하다.

접근 방법

1. brute force로 모든 조합 확인

가장 직접적인 풀이는 중첩 루프로 가능한 모든 두 원소 조합을 확인하는 것이다. 첫 번째 인덱스를 고정하고, 그 뒤에 있는 인덱스를 하나씩 보면서 두 값의 합이 target인지 검사한다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

        return []

이 풀이는 별도의 자료구조가 필요 없어서 공간복잡도는 O(1)이다. 대신 원소가 n개일 때 가능한 쌍을 거의 다 확인할 수 있으므로 시간복잡도는 O(n²)이다.

이 문제를 처음 볼 때 brute force가 자연스럽게 떠오르는 이유는 조건이 단순해서다. 두 값을 더해 target이 되는지만 확인하면 구현 자체는 바로 나오지만, 이미 본 값이나 앞으로 필요한 값을 전혀 기억하지 않기 때문에 같은 배열을 계속 다시 훑는 비용이 생긴다.

2. two-pass hash map

비교를 줄이려면 어떤 값이 어느 인덱스에 있는지 빠르게 찾을 수 있어야 한다. 그래서 먼저 배열을 한 번 순회하면서 값과 인덱스를 hash map에 저장한다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen: dict[int, int] = {}

        for i in range(len(nums)):
            seen[nums[i]] = i

        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in seen and i != seen[complement]:
                return [seen[complement], i]

        return []

여기서 핵심은 complement다. 현재 값이 nums[i]라면, 같이 더해서 target이 되기 위해 필요한 값은 target - nums[i]이고, 그 값이 hash map에 있으면 두 인덱스를 바로 반환할 수 있다.

이 방식은 배열을 두 번 순회하므로 실제 연산은 대략 2n에 가깝지만, Big-O에서는 상수를 버리기 때문에 시간복잡도는 O(n)으로 본다. 대신 값과 인덱스를 저장하는 hash map이 필요하므로 공간복잡도는 O(n)이다.

주의할 점은 같은 원소를 두 번 쓰면 안 된다는 조건이다. 그래서 complement가 hash map에 있더라도 현재 인덱스와 같은 인덱스인지 확인해야 한다. i != seen[complement] 조건이 그 역할을 한다.

3. one-pass hash map

two-pass 방식으로 풀고 나면, 굳이 값을 전부 먼저 저장한 뒤 다시 순회해야 하는지 생각해볼 수 있다. 배열을 왼쪽부터 보면서 “현재 값과 짝이 되는 값이 이전에 있었는지”를 먼저 확인하고, 없으면 현재 값을 저장하면 된다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen: dict[int, int] = {}

        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in seen:
                return [seen[complement], i]

            seen[nums[i]] = i

        return []

이 방식에서는 현재 값을 hash map에 넣기 전에 complement를 먼저 확인한다. 그래서 같은 인덱스를 다시 사용하는 문제가 자연스럽게 사라진다. 현재 원소는 아직 seen에 들어가지 않았고, seen에는 현재 위치보다 앞에서 본 값들만 들어 있기 때문이다.

시간복잡도는 여전히 O(n)이고 공간복잡도도 O(n)이다. two-pass와 Big-O는 같지만, 한 번의 순회 안에서 필요한 값을 확인하고 저장하므로 코드 흐름이 더 간단하다.

복잡도 분석

1. brute force

시간 복잡도: O(n²)
- 가능한 두 원소 조합을 모두 확인할 수 있으므로 비교 횟수가 제곱으로 증가한다.
공간 복잡도: O(1)
- 별도의 자료구조 없이 인덱스 변수만 사용한다.

2. two-pass hash map

시간 복잡도: O(n)
- 배열을 두 번 순회하지만 2n은 Big-O에서 O(n)으로 정리된다.
공간 복잡도: O(n)
- 값과 인덱스를 hash map에 저장한다.

3. one-pass hash map

시간 복잡도: O(n)
- 배열을 한 번 순회하면서 complement 확인과 저장을 처리한다.
공간 복잡도: O(n)
- 최악의 경우 정답을 찾기 전까지 본 값들을 hash map에 저장해야 한다.

최적화 코드

최종적으로는 one-pass hash map 풀이가 가장 자연스럽다. 지금 필요한 complement가 이전에 나왔는지 확인하고, 없으면 현재 값을 이후 원소를 위한 후보로 저장한다.

from typing import List

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen: dict[int, int] = {}

        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in seen:
                return [seen[complement], i]

            seen[nums[i]] = i

        return []

요약 및 회고

이 문제는 hash map을 왜 쓰는지 설명하기 좋은 예제였다. brute force는 두 값을 직접 더해보는 방식이라 가장 단순하지만, 필요한 값을 찾기 위해 배열을 반복해서 확인한다. hash map을 쓰면 현재 값에 필요한 complement가 이미 있었는지 평균 O(1)에 확인할 수 있고, 그 결과 시간복잡도를 O(n²)에서 O(n)으로 줄일 수 있다.

two-pass 풀이를 거쳐 one-pass로 줄여보면, 최적화는 단순히 loop 하나를 없애는 일이 아니었다. 현재 값을 저장하기 전에 complement를 먼저 확인하면 같은 인덱스를 재사용하지 않는 조건까지 자연스럽게 만족한다. 결국 이 문제의 핵심은 두 수를 모두 찾아다니는 것이 아니라, 한 수를 봤을 때 나머지 한 수를 빠르게 찾을 수 있는 상태를 만들어두는 데 있었다.