1. Two Sum (LeetCode)

문제 링크 → LeetCode 1. Two Sum

문제 설명

주어진 정수 배열 nums와 정수 target이 있습니다. 배열 내에서 두 수를 선택하여 더했을 때, 그 합이 target이 되는 두 수의 인덱스를 반환하는 문제입니다. 각 입력값에 정확히 하나의 해가 존재하며, 같은 요소를 두 번 사용할 수 없습니다. 반환하는 인덱스는 순서와 상관 없습니다.

입력

• 정수 배열 nums, 길이 n (2 <= n <= 10^4)
• 정수 target

출력

• 두 정수의 인덱스를 담은 배열

풀이 전략

1. Brute Force — 모든 쌍을 검사. 시간 복잡도 O(n^2).
2. Hash Map — 각 숫자의 인덱스를 저장하면서 보수를 찾음. O(n).

TypeScript 코드

function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>()

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]
    if (map.has(complement)) {
      return [map.get(complement)!, i]
    }
    map.set(nums[i], i)
  }

  throw new Error('No solution found')
}

코드 동작 원리

1. 빈 Hash Map 생성 — 숫자 값을 key, 인덱스를 value로 저장
2. 배열을 순회하며 보수(target - nums[i])를 계산하고 map에 존재하면 정답 반환, 없으면 현재 값 저장
3. 문제 조건상 반드시 정답이 존재하므로 루프 내에서 반환됨

시간/공간 복잡도

구분	복잡도	설명
시간 복잡도	O(n)	배열을 한 번 순회하며, 각 요소에 대해 O(1) 연산 수행
공간 복잡도	O(n)	Hash Map에 최대 n개의 요소 저장

다른 풀이 비교

• Brute Force: 이중 for문으로 모든 쌍을 검사 → O(n^2), O(1)
• 정렬 후 투 포인터: 정렬 시 인덱스가 손실되어 부적절
• Hash Map (현재 방법): O(n) 시간/공간으로 가장 효율적

요점 정리

• Hash Map으로 보수를 빠르게 찾는 것이 핵심
• 시간 복잡도 O(n), 공간 복잡도 O(n)
• 정렬 방식은 인덱스가 바뀌므로 부적합