문제 설명

Two Sum - LeetCode

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

✅ 조건:

  • 각 입력에 정확히 하나의 정답이 존재하며, 같은 요소를 두 번 사용할 수 없음.
  • 정답은 어떤 순서로든 반환 가능함.

해설

1️⃣ 브루트포스 (Brute-force, O(N²))

  • 모든 가능한 두 수의 조합을 탐색하여 target과 비교
  • 시간 복잡도: O(N²) → 비효율적 (배열 크기가 크면 실행 속도가 느림)

2️⃣ 해시맵(HashMap, O(N)) [추천]

  • 한 번의 순회로 해결
  • target - nums[i] 값을 해시맵(dictionary)에 저장하여 빠르게 조회
  • 시간 복잡도: O(N) → 매우 효율적 (빠른 검색 가능)

코드 풀이

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def twoSum(nums, target):
    num_map = {}  # 딕셔너리 (해시맵) 선언

    for i, num in enumerate(nums):
        complement = target - num  # 목표 값에서 현재 숫자를 뺀 값
        
        if complement in num_map:  # 해시맵에서 찾기
            return [num_map[complement], i]
        
        num_map[num] = i  # 현재 숫자 저장

    return []  # 결과가 없을 경우 (문제에서 항상 정답이 존재한다고 가정)

Javascript

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

var twoSum = function(nums, target) {
    let numMap = new Map();  // 해시맵 선언

    for (let i = 0; i < nums.length; i++) {
        let complement = target - nums[i];

        if (numMap.has(complement)) {
            return [numMap.get(complement), i];
        }

        numMap.set(nums[i], i);
    }
    return [];
};

참고 및 출처

programmers Coding Test
LeetCode - The World’s Leading Online Programming Learning Platform