1. Two Sum (LeetCode)

🔗 문제 링크 → LeetCode 1. Two Sum

문제 설명

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

입력

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

출력

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

💡 문제 해결 전략

1. Brute Force (완전 탐색) 방법은 모든 쌍을 검사하여 target과 일치하는지 확인하는 방법입니다. 그러나 시간 복잡도는 O(n²)으로 비효율적입니다.
2. 해시맵 (Hash Map) 을 이용하여, 각 숫자의 인덱스를 저장하면서 현재 숫자의 보수를 빠르게 찾을 수 있습니다. 이 접근법은 O(n)의 시간 복잡도로 효율적입니다.

본 풀이에서는 Hash Map을 이용한 방법을 적용합니다.

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로 저장할 map을 초기화합니다.
2. 배열 순회: nums 배열을 순회하면서 다음을 수행합니다:
   • 현재 숫자의 보수(target - nums[i])를 계산
   • 보수가 map에 존재하는지 확인
     • 존재하면 정답 인덱스 반환
     • 존재하지 않으면 현재 숫자와 인덱스를 map에 저장
3. 반복 종료 후: 문제 조건상 반드시 하나의 정답이 존재하므로, 루프 내에서 반환되지 않는 경우는 없습니다. (다만, 안전성을 위해 에러 처리 추가)

📊 시간 복잡도와 공간 복잡도 분석

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

다른 풀이 방법과 효율성 비교

• Brute Force 방법: 이중 for문으로 모든 쌍을 검사 → 시간 복잡도 O(n²), 공간 복잡도 O(1)
• 정렬 후 투 포인터: 정렬이 필요하나, 인덱스 반환 조건 때문에 부적절 (인덱스 위치 손실됨)
• Hash Map 방법 (현재 방법): O(n) 시간과 공간으로 가장 효율적

📝 요점 정리

• Hash Map을 이용해 보수를 빠르게 찾는 방법이 핵심
• 시간 복잡도 O(n), 공간 복잡도 O(n)
• 정렬 방식은 인덱스가 바뀌기 때문에 부적합
• 가장 효율적이고 직관적인 방법은 Hash Map 활용법