수달씨의 개발공간

[LeetCode] Majority Element - 보이어-무어 투표 알고리즘 (Boyer-Moore Voting Algorithm) 풀이

문제 설명

LeetCode의 "Majority Element" 문제는 배열에서 과반수 요소(majority element)를 찾는 문제입니다.

과반수 요소는 배열 길이 n의 절반(⌊n / 2⌋)을 초과하여 등장하는 요소입니다. 문제에서 항상 과반수 요소가 존재한다고 보장되므로, 이를 활용하여 최적화된 방법을 사용할 수 있습니다.

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

처음에는 각 숫자의 등장 횟수를 카운트해서 가장 많이 등장하는 숫자를 찾으면 되겠다고 생각했어요. 하지만 직접 구현해 보니 추가적인 메모리를 사용해야 했고, 더 최적화할 방법이 필요했습니다.

이 문제에서는 추가 메모리 없이 O(N) 시간 복잡도로 해결 가능한 보이어-무어 투표 알고리즘(Boyer-Moore Voting Algorithm)을 활용할 수 있습니다.

비효율적인 접근 방식 (카운팅을 활용한 풀이)

export function majorityElement(nums: number[]): number {
  const counts: Record<number, number> = {};

  for (const n of nums) {
    counts[n] = (counts[n] || 0) + 1;
  }

  return Object.keys(counts)
    .map(Number)
    .reduce((a, b) => (counts[a] > counts[b] ? a : b));
}

✅ 시간 복잡도 O(N)
❌ 공간 복잡도 O(N) (추가 해시맵 사용)

이 방법도 작동하지만, 공간 복잡도를 최적화할 방법이 필요합니다.

보이어-무어 투표 알고리즘 (Boyer-Moore Voting Algorithm)

이 문제는 과반수 요소가 항상 존재한다는 점을 활용하면, 투표 개념을 적용해서 공간 복잡도를 O(1)로 최적화할 수 있습니다.

✅ 보이어-무어 알고리즘 실행 과정

export function majorityElement(nums: number[]): number {
  let candidate = 0;
  let count = 0;

  for (const num of nums) {
    if (count === 0) {
      candidate = num;  // 새로운 후보 설정
    }
    count += num === candidate ? 1 : -1;  // 같으면 증가, 다르면 감소
  }

  return candidate;
}

✅ 시간 복잡도 O(N)
✅ 공간 복잡도 O(1)
✅ 배열을 한 번만 순회하며 해결 가능

보이어-무어 알고리즘 원리 (쉽게 이해하기)

배열을 투표하는 사람들로 생각해 보자.

• 각 숫자는 후보(candidate) 가 될 수 있음.
• 같은 숫자는 찬성표(++) 를 던지고, 다른 숫자는 반대표(--) 를 던짐.
• 과반수 요소는 항상 절반 이상 존재하므로, 최종적으로 살아남는 후보는 무조건 과반수 요소가 됨.

예제 실행 과정

nums = [2,2,1,1,1,2,2]

단계 현재 숫자 후보(candidate) 개수(count) 설명

✅ 최종 후보: 2 (과반수 요소)

Jest 테스트 코드

describe("Majority Element - Boyer-Moore Voting Algorithm", () => {
  it("returns the majority element from an odd-length array", () => {
    const nums = [3, 2, 3];
    expect(majorityElement(nums)).toEqual(3);
  });

  it("returns the majority element from an even-length array", () => {
    const nums = [2,2,1,1,1,2,2];
    expect(majorityElement(nums)).toEqual(2);
  });

  it("handles an array where all elements are the same", () => {
    const nums = [5, 5, 5, 5, 5, 5, 5];
    expect(majorityElement(nums)).toEqual(5);
  });
});

✅ it 설명을 명확하게 추가하여 테스트의 목적을 알기 쉽게 정리
✅ 다양한 테스트 케이스 추가

결론

처음에는 배열을 순회하며 카운팅하는 방식을 생각했지만, 공간 복잡도를 최적화할 필요가 있었습니다.

보이어-무어 투표 알고리즘은 과반수 요소가 항상 존재한다는 점을 이용하여 최적화할 수 있었습니다. 🎯

이제 과반수 요소를 찾는 문제를 만나면 보이어-무어 알고리즘을 활용해 보세요! 🚀

[LeetCode] Rotate Array - TypeScript 문제 풀이 및 최적화

문제 설명

LeetCode의 "Rotate Array" 문제는 배열을 오른쪽으로 k번 회전하는 문제입니다.

배열을 직접 수정해야 하며, 추가적인 공간을 사용하지 않고 O(1) 공간 복잡도로 해결해야 합니다.

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

처음에는 단순히 배열을 k번 반복해서 이동시키면 되겠다고 생각했어요. 하지만 직접 구현해 보니 비효율적이고 너무 오래 걸린다는 걸 깨달았어요.

이전에는 문제를 풀면서 개선점을 찾아 나가는 방식이었는데, 이번에는 문제의 패턴을 분석한 후 최적화된 방법을 한 번에 떠올렸습니다.

이 문제를 해결하는 과정에서 배열을 회전하는 문제에서 자주 사용되는 "배열 뒤집기" 패턴을 발견할 수 있었습니다.

비효율적인 접근 방식 (배열을 직접 이동시키기)

1️⃣ k번 반복하여 한 칸씩 이동 (O(N * k))

가장 직관적인 해결책은 k번 반복하면서 배열을 오른쪽으로 한 칸씩 이동하는 것입니다.

export function rotate(nums: number[], k: number): void {
  k = k % nums.length; // k가 배열 길이보다 클 경우 처리
  for (let i = 0; i < k; i++) {
    nums.unshift(nums.pop()!);
  }
}

이 방식은 작동은 하지만, 시간 복잡도가 O(N * k)로 매우 비효율적이에요. 배열 길이가 10^5이고 k도 10^5이면, 10^10번 연산해야 하므로 비현실적으로 오래 걸립니다. ❌

최적화 과정: 배열을 한 번에 회전하는 방법 찾기

2️⃣ 추가 배열을 사용 (O(N), O(N))

배열을 복사한 후 (i + k) % n 위치에 배치하면 훨씬 빠르게 해결할 수 있어요.

export function rotate(nums: number[], k: number): void {
  const n = nums.length;
  const rotated = new Array(n);
  
  for (let i = 0; i < n; i++) {
    rotated[(i + k) % n] = nums[i];
  }

  for (let i = 0; i < n; i++) {
    nums[i] = rotated[i];
  }
}

✅ 시간 복잡도 O(N), 공간 복잡도 O(N)
❌ 추가 배열 사용 → 공간 최적화 필요

3️⃣ 배열 뒤집기를 이용한 최적화 (O(N), O(1))

배열을 직접 이동하지 않고, 배열을 뒤집는 방식으로 해결할 수 있을까? 🤔

핵심 패턴 발견

배열을 k번 회전하는 건 두 개의 블록을 서로 교체하는 것과 같다!

nums = [1,2,3,4,5,6,7], k = 3
결과:    [5,6,7,1,2,3,4]

💡 배열을 3개의 부분으로 나눠서 뒤집으면 해결 가능!

1. 배열 전체를 뒤집는다 → [7,6,5,4,3,2,1]
2. 처음 k개의 원소를 다시 뒤집는다 → [5,6,7,4,3,2,1]
3. 나머지 n-k개의 원소를 다시 뒤집는다 → [5,6,7,1,2,3,4]

✅ 이제 정답이 나왔다!

최적화된 TypeScript 풀이 (O(N), O(1))

export function rotate(nums: number[], k: number): void {
  k = k % nums.length; // 배열 길이를 초과하는 k 처리

  function reverse(start: number, end: number) {
    while (start < end) {
      [nums[start], nums[end]] = [nums[end], nums[start]];
      start++;
      end--;
    }
  }

  reverse(0, nums.length - 1);  // 배열 전체 뒤집기
  reverse(0, k - 1);            // 처음 k개 뒤집기
  reverse(k, nums.length - 1);  // 나머지 뒤집기
}

✅ 시간 복잡도 O(N), 공간 복잡도 O(1)
✅ 추가 배열 없이 제자리에서 해결 가능
✅ 배열 뒤집기 패턴을 활용한 최적화된 방식

Jest 테스트 코드

describe("Medium 189: Rotate Array", () => {
  it("rotates an array of length 7 by 3 positions", () => {
    const nums = [1, 2, 3, 4, 5, 6, 7];
    rotate(nums, 3);
    expect(nums).toEqual([5, 6, 7, 1, 2, 3, 4]);
  });

  it("rotates an array of length 4 by 2 positions", () => {
    const nums = [-1, -100, 3, 99];
    rotate(nums, 2);
    expect(nums).toEqual([3, 99, -1, -100]);
  });
});

✅ it 설명을 배열 크기 + 회전 횟수 기준으로 작성하여 가독성 향상
✅ 추가적인 엣지 케이스도 테스트 가능

결론

이전에는 문제를 해결한 후 개선점을 찾아가며 최적화하는 방식이었어요. 하지만 이번에는 배열 회전의 패턴을 분석한 후 최적화된 방법을 한 번에 떠올릴 수 있었습니다. 🎯

배열 뒤집기 패턴은 회전 관련 문제에서 자주 사용되는 패턴이므로 기억해 두면 좋습니다! 🚀

[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 알고리즘 문제 풀이를 더 효율적으로 작성하는 방법을 배웠습니다! 🚀

[LeetCode] Remove Element - TypeScript 문제 풀이 및 최적화

문제 설명

LeetCode의 "Remove Element" 문제는 배열 nums에서 특정 값 val을 제거하고, 남은 요소의 개수를 반환하는 문제입니다.

배열을 직접 수정해야 하며, 순서는 바뀌어도 무관합니다. 반환값으로는 유효한 길이를 제공합니다.

문제를 처음 접했을 때 어려웠던 점

처음에는 단순히 val을 제거하는 문제라고 생각했는데, 실제로는 맨 끝 요소와 바꿔가면서 해결해야 하는 문제였습니다. 처음 문제를 풀 때는 배열에서 val을 그냥 지우려고 했지만, 삭제하는 방식으로는 올바르게 해결되지 않았습니다.

배열의 순서를 유지할 필요가 없기 때문에 맨 끝 요소와 교환하며 해결하는 방식을 이해하는 것이 핵심이었습니다.

최적화된 TypeScript 풀이

문제를 올바르게 해결하기 위해 두 개의 포인터를 사용하여 val을 배열의 끝으로 보내는 방식으로 구현했습니다.

export function removeElement(nums: number[], val: number): number {
  let right = nums.length - 1;
  let index = 0;

  while (index <= right) {
    if (nums[index] === val) {
      nums[index] = nums[right]; // `right`의 값을 `index`에 덮어쓰기
      right--; // right를 줄여 제거한 효과
    } else {
      index++; // val이 아닐 때만 index 증가
    }
  }

  return right + 1; // 유효한 길이 반환
}

코드의 핵심 개념

✅ 배열의 순서를 유지할 필요가 없으므로, 뒤쪽 요소와 교환 가능
✅ 앞에서부터 순회하며 val을 만나면 맨 끝 요소와 교환
✅ 반환값은 유효한 요소 개수 (right + 1)

Jest 테스트 코드

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

describe("LeetCode 27: Remove Element", () => {
  it("removes all instances of 3", () => {
    const input = [3,2,2,3];
    const result = removeElement(input, 3);
    expect(result).toEqual(2);
    expect(input.slice(0, result).sort()).toEqual([2, 2]);
  });

  it("removes all instances of 2", () => {
    const input = [0,1,2,2,3,0,4,2];
    const result = removeElement(input, 2);
    expect(result).toEqual(5);
    expect(input.slice(0, result).sort()).toEqual([0, 0, 1, 3, 4]);
  });

  it("handles an array with no occurrences", () => {
    const input = [1, 3, 5, 7];
    const result = removeElement(input, 2);
    expect(result).toEqual(4);
    expect(input.slice(0, result)).toEqual([1, 3, 5, 7]);
  });

  it("handles an empty array", () => {
    const input: number[] = [];
    const result = removeElement(input, 1);
    expect(result).toEqual(0);
    expect(input).toEqual([]);
  });
});

✅ 다양한 테스트 케이스 추가 → 엣지 케이스(빈 배열, 없는 값 등)까지 검증
✅ 배열의 순서가 바뀌어도 정답이므로 sort()로 정렬하여 검증
✅ result를 활용한 직관적인 검증 → input.slice(0, result)로 올바른 요소 확인

결론

처음에는 val을 배열에서 단순히 제거하는 문제라고 생각했지만, 실제로는 맨 끝 요소와 바꾸면서 해결하는 문제였습니다. 이 점을 이해하는 것이 가장 어려웠고, 이후에는 두 개의 포인터를 활용하여 깔끔하게 해결할 수 있었습니다.

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

[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 테스트 코드 적용