Algorithm/LeetCode

[LeetCode 167] Two Sum II - Input Array Is Sorted

개발하는 수달씨 2025. 3. 28. 08:26
반응형

LeetCode 167: Two Sum II - Input Array Is Sorted

📌 문제 설명

주어진 정렬된 배열에서 두 숫자의 합이 주어진 target과 일치하는 인덱스를 반환하는 문제입니다.
배열의 인덱스는 1부터 시작하고, 합이 일치하는 두 숫자의 인덱스를 1-based로 반환해야 합니다.

✅ 풀이 아이디어: Two Pointers 알고리즘

이 문제는 Two Pointers 기법을 사용하여 해결할 수 있습니다.

  1. 배열이 정렬되어 있음을 이용해 left 포인터는 배열의 앞에서 시작하고, right 포인터는 배열의 끝에서 시작합니다.
  2. 두 포인터의 합이 target보다 작으면 left를 증가시키고, 합이 크면 right를 감소시킵니다.
  3. 두 포인터가 가리키는 값이 합이 target과 같다면 그 인덱스를 반환합니다.
  4. 이러한 방식으로 한 번 순회하여 문제를 해결할 수 있습니다. 이때 **시간 복잡도는 O(n)**입니다.

✅ 구현 코드 (TypeScript)

export function twoSum(numbers: number[], target: number): number[] {
  let left = 0;
  let right = numbers.length - 1;

  while (left < right) {
    const sum = numbers[left] + numbers[right];

    if (sum === target) {
      return [left + 1, right + 1]; // 1-based index
    }

    if (sum < target) {
      left++; // 합이 target보다 작으면 left 포인터를 증가
    } else {
      right--; // 합이 target보다 크면 right 포인터를 감소
    }
  }

  return [];
}

✅ 테스트 코드 (Jest)

describe("Medium 167: Two Sum II", () => {
  it("should return [1, 2] for [2, 7, 11, 15] and target 9", () => {
    expect(twoSum([2, 7, 11, 15], 9)).toEqual([1, 2]);
  });

  it("should return [1, 2] for [-1, 0] and target -1", () => {
    expect(twoSum([-1, 0], -1)).toEqual([1, 2]);
  });

  it("should return [1, 3] for [2, 3, 4] and target 6", () => {
    expect(twoSum([2, 3, 4], 6)).toEqual([1, 3]);
  });
});

✅ 시간 복잡도

  • 시간 복잡도: O(n)
    • 배열을 한 번만 순회하므로, 시간 복잡도는 배열의 길이에 비례하여 선형입니다.
  • 공간 복잡도: O(1)
    • 추가적인 공간을 사용하지 않으므로 공간 복잡도는 상수입니다.

✅ 마무리

이 문제를 풀면서 중간 난이도 문제도 이제는 한 번에 풀 수 있게 된 것 같다는 자신감이 생겼습니다.
Two Pointers 알고리즘을 통해 정렬된 배열에서 빠르게 답을 찾는 기법을 잘 활용한 문제였습니다. 이제는 이런 유형의 문제를 더 잘 풀 수 있을 것 같아요.

반응형