[Grind75] Two Sum

✏️ LeetCode 001: Two Sum

• Level: Easy
• Pattern: Hash Map
• Language: Python3

문제 요약

정수 배열에서 합이 target 이 되는 두 수의 인덱스를 찾는 문제.
같은 원소를 두 번 사용할 수 없고, 정답은 하나만 존재한다.

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]

시간복잡도

• O(n^2)

특징

• 가장 직관적이다.
• 구현은 쉽지만 비효율적이다.

2. Hash Map 풀이

아이디어

현재 값 n 을 볼 때, target - n 값이 이전에 나왔는지 확인한다.
즉, 현재 값의 짝(complement)이 과거에 있었는지 찾는 방식이다.

코드

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        index_map = {}

        for i, value in enumerate(nums):
            complement = target - value

            if complement in index_map:
                return [index_map[complement], i]

            index_map[value] = i

시간복잡도

• O(n)

특징

• 한 번의 순회로 해결 가능하다.
• 코딩테스트에서 자주 나오는 정석 풀이이다.

이 문제의 암기 포인트

• complement = target - value
• 현재 값의 짝이 이전에 있었는지 확인한다.
• 먼저 찾고, 나중에 저장한다.
• index_map 은 과거 값 저장용이다.
• value -> index 형태로 저장한다.

언제 Hash Map을 떠올릴까?

아래 같은 키워드가 보이면 hash map 패턴을 먼저 의심한다.

• 어떤 값이 이미 나왔는지 빠르게 확인해야 할 때
• 중복 검사가 필요할 때
• 값의 존재 여부를 바로 알아야 할 때
• 두 값의 pair / target / complement 관계를 찾아야 할 때
• 빈도 수 / 매칭 / 인덱스 저장이 필요한 문제일 때

한 줄 요약

Two Sum은 모든 쌍을 비교하는 brute force 문제를,
Hash Map으로 O(n)까지 줄이는 대표 문제다.

Always remember

• Hash Map
• value -> index
• complement = target - value
• one-pass
• find first, then save