LeetCode: Two Sum

Two Sum 문제 풀이: 두 가지 접근법

문제 설명

https://leetcode.com/problems/two-sum/

 

배열 nums와 정수 target이 주어졌을 때, 합이 target이 되는 두 숫자의 인덱스를 반환하는 문제입니다.

• 각 입력은 하나의 정답을 가지며, 동일한 요소를 두 번 사용할 수 없습니다.
• 반환값은 인덱스 쌍으로, 순서는 상관없습니다.

---

1. 브루트포스(Brute Force) 방법

첫 번째로 떠오르는 직관적인 접근법은 모든 가능한 쌍을 검사하는 것입니다.
이 방법은 단순하지만, 시간 복잡도가 높아 효율적이지 않습니다.

시간 복잡도

• O(n²): 모든 요소를 두 번 반복하며 쌍을 검사하기 때문입니다.

고랭 코드

func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil // 답이 항상 존재하므로 실제로 실행되지 않음
}

자바 코드

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        return null; // 답이 항상 존재하므로 실제로 실행되지 않음
    }
}

장단점

• 장점: 간단하고 구현이 쉽습니다.
• 단점: 비효율적이며, 대규모 입력에 대해 매우 느립니다.

---

2. 해시맵(HashMap)을 이용한 최적화

두 번째 접근법은 해시맵(Go에서는 맵, Java에서는 HashMap)을 이용해 숫자의 인덱스를 저장하고, 현재 숫자에 필요한 "짝을" 빠르게 찾는 방식입니다.

동작 원리

1. 배열을 한 번만 순회하면서, 각 숫자를 해시맵에 추가합니다.
2. 현재 숫자에 필요한 짝 = target - nums[i]가 해시맵에 존재하는지 확인합니다.
   • 존재하면 인덱스 쌍을 반환합니다.
   • 존재하지 않으면 현재 숫자를 해시맵에 저장하고 다음으로 진행합니다.

시간 복잡도

• O(n): 배열을 한 번만 순회하기 때문에 효율적입니다.

고랭 코드

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    for i, num := range nums {
        complement := target - num
        if idx, found := numMap[complement]; found {
            return []int{idx, i} // 짝을 찾으면 반환
        }
        numMap[num] = i // 현재 숫자를 해시맵에 추가
    }
    return nil
}

속도가 엄청 향상된걸 볼 수 있다..! 😀

자바 코드

import java.util.HashMap;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> numMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (numMap.containsKey(complement)) {
                return new int[]{numMap.get(complement), i}; // 짝을 찾으면 반환
            }
            numMap.put(nums[i], i); // 현재 숫자를 해시맵에 추가
        }
        return null; // 답이 항상 존재하므로 실제로 실행되지 않음
    }
}

장단점

• 장점: 효율적이고, 대규모 입력에서도 성능이 우수합니다.
• 단점: 약간 더 복잡한 로직과 메모리 사용량 증가(HashMap 저장).

---

왜 해시맵을 사용해야 할까요?

1. 빠른 검색 속도: 해시맵은 평균적으로 O(1) 시간에 키를 검색할 수 있습니다.
2. 필요한 값만 저장: 과거의 숫자와 인덱스만 저장하므로 불필요한 연산이 줄어듭니다.
3. 배열 전체를 두 번 순회하지 않아도 됨: 브루트포스와 비교해 두 숫자 합을 찾는 연산이 즉각적입니다.

---

최종 비교

---

마무리

이 블로그 글을 통해 Two Sum 문제를 단순한 접근법에서 최적화된 방법으로 해결하는 과정을 배우셨을 겁니다. 특히 해시맵의 강력한 검색 속도를 활용하면 효율적인 알고리즘 설계가 가능하다는 것을 알 수 있습니다.