1. Two Sum

 

📌 Problem Link :

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

✅ Accepted :

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        int n = nums.length;

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            map.put(nums[i], i);
        }

        int key = 0;
        for (int i = 0; i < n; i++) {
            key = target - nums[i];
            if (map.containsKey(key) && map.get(key) != i) {
                answer[0] = i;
                answer[1] = map.get(key);
                break;
            }
        }
        return answer;
    }
}

🧐 Review :

Two Sum 문제는 nums 배열에서 target을 만들 수 있는 두 수의 인덱스를 찾는 전형적인 문제입니다.

입력 길이가 최대 10^4이기 때문에, 단순히 모든 쌍을 확인하는 O(N^2) 방식으로 접근하면 시간 초과가 날 가능성이 높습니다. 그래서 처음에는 더 효율적인 방법을 고민하면서 문제를 시작했습니다.

1. 처음 떠올린 접근: 정렬 + 투 포인터

가장 먼저 떠올린 방법은 nums를 정렬한 뒤 투 포인터로 두 값을 찾아가는 방식이었습니다.

하지만 이 문제에는 큰 제약이 하나 있습니다.

 

정답으로 반환해야 하는 것은 “값”이 아니라 “원래 인덱스”라는 점입니다.

 

배열이 정렬되는 순간 원래 인덱스 정보가 사라지기 때문에, 정렬 기반 접근은 인덱스를 따로 저장하는 구조를 만들지 않는 이상 단순하게 해결하기 어렵습니다.

특히 Java에서는 파이썬처럼 (값, 인덱스) 형태의 튜플을 쉽게 만들고 정렬하는 패턴이 익숙하지 않아, 이 방법은 오히려 구현이 더 복잡해질 것 같았습니다.

그래서 이 방법은 곧바로 제외했고, 다른 풀이를 찾기로 했습니다.

 

---

2. 문제의 토픽에서 힌트 얻기: Hash Table 활용

문제 페이지의 토픽과 힌트를 확인해보니 “Hash Table”이 포함되어 있었습니다.

처음에는 딱 떠오르는 구조는 없었지만, 힌트를 참고하면서 “보완값(complement)을 빠르게 찾는 방식”을 적용할 수 있겠다는 생각이 들었습니다.

 

제가 처음 작성한 풀이는 다음과 같은 방식입니다.

 

1. 첫 번째 루프에서 배열의 모든 값과 인덱스를 해시맵에 저장한다.
2. 두 번째 루프에서 각 값에 대해 key = target - nums[i] 를 계산하고,
3. 그 값이 맵에 존재하면 두 인덱스를 반환한다.

 

✔️ 동작은 정확하고 모든 테스트 케이스를 통과할 수 있습니다.

다만 한 가지 아쉬운 점이 있는데, 바로 배열을 두 번 순회한다는 점입니다.

 

---

3. 리트코드 풀이: One-pass Hash Table

리트코드에서 공개한 가장 대표적인 풀이가 바로 One-pass Hash Table 방식입니다.

이 방식은 제 풀이와 다르게, 배열을 단 한 번만 순회하면서 정답을 찾습니다.

 

원리는 단순합니다.

 

1. 현재 값을 기준으로 필요한 보완값(complement)이 맵에 있는지 먼저 확인한다.
2. 없다면 이제서야 현재 값을 맵에 넣는다.
3. 있다면 바로 정답이므로 두 인덱스를 반환한다.

 

이 방식의 장점은 다음과 같습니다.

 

• 정답이 배열 앞쪽에 있을 때 즉시 종료가 가능하다.
• 별도의 선행 작업(전체 맵 생성)이 필요 없다.
• 코드가 더 간결하다.

 

제가 작성한 두-pass 방식도 시간 복잡도는 O(N)이지만,

읽는 사람 입장에서는 one-pass 풀이가 훨씬 직관적인 흐름을 가진다는 점에서 더 좋은 선택이라고 느껴졌습니다.

🏷️ Reference:

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
        // Return an empty array if no solution is found
        return new int[] {};
    }
}