수달씨의 개발공간

[LeetCode] Remove Duplicates from Sorted Array II - TypeScript 문제 풀이 및 개선 과정

문제 설명

LeetCode의 "Remove Duplicates from Sorted Array II" 문제는 정렬된 배열에서 각 원소가 최대 2번까지만 포함되도록 중복을 제거하는 문제입니다.

배열을 직접 수정해야 하며, 중복을 제거한 후에도 배열 크기는 유지되어야 합니다. 반환값으로 유효한 배열 길이를 제공합니다.

처음 풀이

먼저, 문제를 해결하기 위해 다음과 같은 코드를 작성했습니다.

export function removeDuplicates(nums: number[]): number {
  let current = 1;
  for (let index = 2; index < nums.length; index++) {
    const val = nums[index];
    const prev1 = nums[current];
    const prev2 = nums[current - 1];

    if (prev1 !== val) {
      current++;
      nums[current] = val;
    } else if (prev2 !== val) {
      current++;
      nums[current] = val;
    }
  }
  return current + 1;
}

초기 코드 분석

✅ prev1과 prev2를 비교하여 현재 숫자가 2번 이하로 등장하는지 검사
✅ 유효한 경우 current 포인터를 이동하며 중복을 제거
❌ if-else 문이 불필요하게 많아 코드가 복잡함
❌ current + 1을 반환하는 방식이 직관적이지 않음

위 코드도 정답이지만, 개선할 여지가 있어 보였습니다.

개선 과정

문제점을 정리해보니, 두 가지 부분을 최적화할 수 있었습니다.

1. current = 1 대신 current = 2로 설정하면 처음 두 개의 원소는 자동으로 유지됩니다.
2. prev1과 prev2를 비교하는 if-else 구조를 단순화하면 코드가 더 깔끔해집니다.

이를 반영하여 최적화된 코드를 작성했습니다.

최적화된 TypeScript 풀이

export function removeDuplicates(nums: number[]): number {
  let current = 2; // 처음 두 개의 원소는 무조건 유지
  for (let index = 2; index < nums.length; index++) {
    if (nums[index] !== nums[current - 2]) {
      nums[current] = nums[index];
      current++;
    }
  }
  return current;
}

개선된 코드의 장점

✅ 초기값 설정 개선: current = 2로 설정하여 처음 두 개의 원소를 자동으로 유지
✅ 불필요한 조건문 제거: prev2 !== val만 검사하면 되므로 코드가 단순해짐
✅ 가독성 향상: current 자체를 반환하여 코드가 직관적임
✅ 성능 최적화: 조건문이 줄어들어 실행 속도가 미세하게 향상됨

Jest 테스트 코드

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

describe("Medium 80: Remove Duplicates from Sorted Array II", () => {
  it("removes duplicates allowing at most twice per element", () => {
    const input = [1, 1, 1, 2, 2, 3];
    const result = removeDuplicates(input);
    expect(result).toEqual(5);
    expect(input.slice(0, result)).toEqual([1, 1, 2, 2, 3]);
  });

  it("removes duplicates from a larger input", () => {
    const input = [0, 0, 1, 1, 1, 1, 2, 3, 3];
    const result = removeDuplicates(input);
    expect(result).toEqual(7);
    expect(input.slice(0, result)).toEqual([0, 0, 1, 1, 2, 3, 3]);
  });

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

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

✅ 명확한 테스트 설명 추가: it 블록에 구체적인 설명을 추가해 테스트 목적을 쉽게 이해할 수 있음.
✅ 다양한 입력 케이스 추가: 엣지 케이스(빈 배열, 모든 원소가 같은 경우 등)도 포함하여 코드가 안전하게 동작하는지 검증함.
✅ result를 활용하여 직관적인 검증: input.slice(0, result) 방식을 적용해 최종 배열이 올바르게 변경되었는지 확인.

결론

처음에는 prev1, prev2를 따로 체크하며 중복을 제거하는 방식을 사용했지만, 이를 단순화하여 더 직관적이고 최적화된 코드로 개선했습니다.

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

SEO 키워드

✅ Remove Duplicates from Sorted Array II
✅ LeetCode TypeScript 문제 풀이
✅ TypeScript 중복 제거 알고리즘
✅ LeetCode Top Interview 150 풀이
✅ O(N) 최적화된 중복 제거 코드
✅ Jest 테스트 코드 적용