[LeetCode 26] Remove Duplicates from Sorted Array - TypeScript 문제 풀이 및 최적화

[LeetCode] Remove Duplicates from Sorted Array - TypeScript 문제 풀이 및 최적화

문제 설명

LeetCode의 "Remove Duplicates from Sorted Array" 문제는 정렬된 배열에서 중복된 요소를 제거하고, 남은 요소의 개수를 반환하는 문제입니다.

배열을 직접 수정해야 하며, 추가적인 공간을 사용하지 않고 O(1) 공간 복잡도로 해결해야 합니다. 반환값으로는 중복 제거 후 남은 요소의 개수를 제공합니다.

---

처음 문제를 풀었을 때의 생각

이전에는 코드를 작성한 후 개선점을 찾아가면서 최적화하는 방식으로 문제를 해결했어요. 그런데 이번에는 문제를 분석한 후 바로 최적화된 코드가 한 번에 떠올랐습니다. 이전보다 문제 해결 능력이 향상된 것을 느낄 수 있었어요. 🚀

이 문제는 배열이 정렬되어 있다는 점을 활용하면 효율적으로 해결할 수 있습니다. 중복된 값이 나오면 무시하고, 중복이 아닌 값만 순차적으로 채워 넣는 방식을 사용하면 됩니다.

---

최적화된 TypeScript 풀이

export function removeDuplicates(nums: number[]): number {
  let current = 0;
  for (const n of nums) {
    if (nums[current] === n) continue;
    nums[++current] = n;
  }
  return current + 1;
}

코드의 핵심 개념

✅ 배열이 정렬되어 있으므로 중복이 연속적으로 등장한다는 점 활용
✅ 새로운 중복되지 않은 값이 나오면 current를 증가시키고 해당 위치에 저장
✅ 최종적으로 current + 1을 반환하여 남은 요소 개수를 리턴

---

Jest 테스트 코드

코드의 정확성을 검증하기 위해 Jest 테스트 코드를 작성했습니다.

describe("Easy 26: Remove Duplicates from Sorted Array", () => {
  it("removes duplicates from a short sorted array", () => {
    const input = [1, 1, 2];
    const ret = removeDuplicates(input);
    expect(ret).toEqual(2);
    expect(input.slice(0, ret)).toEqual([1, 2]);
  });

  it("removes duplicates from a longer sorted array", () => {
    const input = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
    const ret = removeDuplicates(input);
    expect(ret).toEqual(5);
    expect(input.slice(0, ret)).toEqual([0, 1, 2, 3, 4]);
  });

  it("handles an already unique array", () => {
    const input = [1, 2, 3, 4, 5];
    const ret = removeDuplicates(input);
    expect(ret).toEqual(5);
    expect(input.slice(0, ret)).toEqual([1, 2, 3, 4, 5]);
  });

  it("handles an array with all duplicates", () => {
    const input = [2, 2, 2, 2, 2];
    const ret = removeDuplicates(input);
    expect(ret).toEqual(1);
    expect(input.slice(0, ret)).toEqual([2]);
  });
});

✅ 각 테스트의 목적을 명확히 설명 → it("...")에 의미 있는 설명 추가
✅ 다양한 엣지 케이스 추가 → 중복 없는 배열, 모든 값이 같은 배열까지 검증
✅ expect(input.slice(0, ret))을 활용해 최종 배열 검증

---

결론

이전에는 코드를 여러 번 수정하면서 최적화를 해나갔는데, 이번에는 처음부터 가장 효율적인 코드가 한 번에 작성되었다는 점이 흥미로웠어요. 🎯

이 문제에서는 배열이 정렬되어 있다는 특징을 활용하는 것이 핵심이었습니다.

이제 TypeScript 알고리즘 문제 풀이를 더 효율적으로 작성하는 방법을 배웠습니다! 🚀