Two Sum

문제

정수 배열 nums와 목표 정수 target이 주어집니다. 배열 내의 두 숫자를 더해 target이 될 수 있도록 하는 두 숫자의 인덱스를 배열에 담아 반환하는 프로그램을 작성하는 문제입니다.

• 단, 정확히 하나의 정답만 존재한다고 가정합니다.
• 동일한 원소를 중복해서 사용할 수 없습니다.
• 정답의 순서는 상관없습니다.

제한사항 (Constraints)

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

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

풀이 1: 브루트 포스 (Brute Force)를 이용한 완전 탐색

가장 직관적인 방법으로, 이중 반복문을 사용하여 가능한 모든 두 숫자의 쌍을 확인하는 방식입니다.

• 탐색 로직: 기준이 되는 숫자(nums[i])를 차례대로 순회하며, 그 뒤에 있는 숫자(nums[j])들과 일일이 더해봅니다.
• 정답 반환: 두 숫자의 합이 target과 일치하는 순간, 두 숫자의 인덱스인 i와 j를 배열에 담아 반환합니다.
• 한계점: 모든 쌍을 다 확인해야 하므로 배열의 길이가 길어질수록 탐색 시간이 기하급수적으로 늘어납니다. (시간 복잡도: O(N^2))

코드 1

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 첫 번째 숫자 선택
        for (int i = 0; i < nums.length - 1; i++) {
            // 두 번째 숫자 선택 (첫 번째 숫자 이후의 값들만 확인)
            for (int j = i + 1; j < nums.length; j++) {
                // 두 수의 합이 target과 같은지 확인
                if (target == nums[i] + nums[j]) {
                    return new int[]{i, j};
                }
            }
        }

        return null;
    }
}

풀이 2: HashMap을 활용한 O(N) 최적화

이중 반복문의 비효율성을 극복하기 위해 HashMap을 활용하여 탐색 속도를 대폭 개선한 방식입니다.

• 핵심 아이디어: 두 수의 합이 target이 되어야 하므로, 현재 숫자 nums[i]를 확인하고 있을 때 우리가 찾아야 하는 나머지 짝은 무조건 target - nums[i]가 됩니다.
• 해시맵(HashMap) 활용: 1. 배열을 한 번만 순회합니다. (for문 1개) 2. 현재 숫자의 짝(target - nums[i])이 이미 HashMap에 저장되어 있는지 containsKey로 확인합니다. 3. 존재한다면, 짝의 인덱스와 현재 인덱스 i를 즉시 반환합니다. 4. 존재하지 않는다면, 다음 숫자의 짝이 될 수 있도록 현재 숫자와 그 인덱스를 HashMap에 저장(put)해 둡니다.
• 효율성: 배열을 단 한 번만 순회하며, 해시맵에서의 검색은 평균적으로 O(1)의 시간이 걸리므로 전체 시간 복잡도를 O(N)으로 획기적으로 단축할 수 있습니다.

코드 2

import java.util.*;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int i = 0; i < nums.length; i++) {
            // 현재 숫자의 짝(target - nums[i])이 맵에 존재하는지 확인
            if (map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i) {
                return new int[]{i, map.get(target - nums[i])}; // 짝이 존재하면 [현재 인덱스, 짝의 인덱스] 반환
            }
            
            // 짝이 없다면 현재 숫자와 인덱스를 맵에 저장
            map.put(nums[i], i);
        }

        return null;
    }
}

알고리즘 분류

배열 (Array), 해시 테이블 (Hash Table), 브루트 포스 (Brute Force)