1. Two Sum (LeetCode)

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

1. 직관적인 출발: 브루트 포스 (Brute Force)

가장 먼저 떠올릴 수 있는 가장 직관적인 접근법입니다. 배열 내의 모든 가능한 두 수의 조합을 이중 루프(for문)로 전부 확인하며 합이 target이 되는지 검사합니다.

• 시간 복잡도: $O(N^2)$ (구체적으로는 $\frac{N(N-1)}{2}$번 연산)
• 특징: 누구나 쉽게 구현할 수 있고 문제 이해의 출발점이 되지만, 배열의 크기가 크면 시간 초과가 발생할 위험이 있습니다.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    const n = nums.length;

    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
};

2. 정렬과 투 포인터 (Two Pointers)

$O(N^2)$보다 빠르게 개선하려면 $O(N \log N)$이나 $O(N)$으로 줄여야 합니다. $O(N \log N)$이라는 숫자를 보는 순간 자연스럽게 '정렬'이 떠올랐고, 정렬된 배열이라면 양 끝에서 접근하는 '투 포인터' 알고리즘으로 $O(N)$ 만에 답을 찾을 수 있다고 생각했습니다.

• 핵심 로직:
  1. 가장 작은 값(left)과 가장 큰 값(right)의 합을 target과 비교합니다.
  2. 합이 target보다 작다면 더 큰 값이 필요하므로 left를 오른쪽으로 이동합니다.
  3. 합이 target보다 크다면 더 작은 값이 필요하므로 right를 왼쪽으로 이동합니다.
• 넘어야 할 과제 (인덱스 유실):
• 이 문제의 정답은 '숫자'가 아닌 '원래 배열의 인덱스'입니다. 단순히 배열을 정렬하면 원래 인덱스 정보가 섞여서 사라집니다. 이를 해결하기 위해 [값, 원래 인덱스] 형태의 쌍(Pair)으로 매핑한 후 정렬을 진행했습니다.
• 시간 복잡도: 정렬 $O(N \log N)$ + 투 포인터 탐색 $O(N) \Rightarrow$ 최종 $O(N \log N)$

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    const n = nums.length;

    const numsAndIdx = nums.map((num, i) => [num, i]);
    numsAndIdx.sort((a, b) => a[0] - b[0]);
    console.log({ numsAndIdx })

    let left = 0;
    let right = n - 1;

    while (left < right) {
        const a = numsAndIdx[left];
        const b = numsAndIdx[right];

        const sum = a[0] + b[0]

        if (sum === target) {
            const answer = [a[1], b[1]];
            answer.sort((a, b) => a - b)
            return answer
        } else if (sum < target) {
            left++
        } else {
            right--
        }
    }
};

3. 공간을 팔아 시간을 얻다: 해시맵 (Hash Map)

해시맵은 데이터 삽입/조회가 평균 $O(1)$입니다. 배열을 단 한 번만 순회($O(N)$)하면서 해시맵을 활용하면 최종 시간 복잡도를 $O(N)$까지 낮출 수 있습니다.

• 발상의 전환 (One-pass 탐색):이를 해결하기 위해 해시맵 구성과 답 탐색을 배열 순회와 동시에 진행(One-pass)했습니다.
• 처음에는 모든 요소를 해시맵에 미리 다 넣어두고 시작하려 했습니다. 하지만 배열에 중복된 숫자가 존재할 경우, 해시맵의 키(Key)가 덮어씌워져 인덱스 관리가 복잡해지는 문제가 있었습니다.
• 핵심 로직:
  1. 현재 숫자(num)를 볼 때, 필요한 보완값(target - num)이 이미 해시맵에 있는지 확인합니다.
  2. 있다면? 이미 지나온 과거의 인덱스와 현재 인덱스가 정답이므로 즉시 반환합니다.
  3. 없다면? 나중에 올 다른 숫자의 보완값이 될 수 있도록 현재 숫자와 인덱스를 해시맵에 등록합니다.
• 시간 복잡도: $O(N)$ (공간 복잡도 역시 해시맵 사용으로 $O(N)$)

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
    const n = nums.length;

    const map = new Map();
    for (let i = 0; i < n; i++) {
        const complement = target - nums[i];

        if (map.has(complement)) {
            return [map.get(complement), i]
        } else {
            map.set(nums[i], i)
        }
    }
};