TypeScript로 LeetCode 28번 해결! 문자열 검색 알고리즘 (KMP, Rabin-Karp)

🔍 LeetCode 28번 - Find the Index of the First Occurrence in a String (TypeScript)

LeetCode 28번 문제는 문자열 검색 알고리즘을 활용하여 특정 문자열(needle)이 다른 문자열(haystack) 내에서 처음 등장하는 위치를 찾는 문제입니다.
이 글에서는 여러 가지 알고리즘을 사용하여 TypeScript로 해결하는 방법을 설명합니다.

---

1️⃣ Brute Force (기본 구현) - O(N*M)

가장 단순한 방법은 Brute Force (완전 탐색) 방식으로, haystack을 순차적으로 검사하며 needle과 일치하는 부분을 찾습니다.

export function strStr(haystack: string, needle: string): number {
  for (let index = 0; index < haystack.length - needle.length + 1; index++) {
    if (haystack.slice(index, index + needle.length) === needle) {
      return index;
    }
  }
  return -1;
}

✅ 특징

• O(N*M)의 시간 복잡도를 가짐 (N: haystack 길이, M: needle 길이)
• 작은 입력에서는 충분히 빠름
• 하지만 긴 문자열에서는 비효율적

---

2️⃣ KMP 알고리즘 (Knuth-Morris-Pratt) - O(N+M)

KMP 알고리즘은 LPS (Longest Prefix Suffix) 배열을 사용하여 중복된 비교를 방지하여 성능을 향상시킵니다.

export function strStrKMP(haystack: string, needle: string): number {
  if (needle === "") return 0;

  const lps = new Array(needle.length).fill(0);
  let j = 0;

  // LPS 배열 생성
  for (let i = 1; i < needle.length; i++) {
    while (j > 0 && needle[i] !== needle[j]) {
      j = lps[j - 1];
    }
    if (needle[i] === needle[j]) {
      j++;
      lps[i] = j;
    }
  }

  // 문자열 검색
  j = 0;
  for (let i = 0; i < haystack.length; i++) {
    while (j > 0 && haystack[i] !== needle[j]) {
      j = lps[j - 1];
    }
    if (haystack[i] === needle[j]) {
      j++;
      if (j === needle.length) {
        return i - j + 1;
      }
    }
  }

  return -1;
}

✅ 장점: O(N+M)의 시간 복잡도로 빠름
✅ 단점: LPS 배열을 먼저 만들어야 해서 코드가 조금 길어짐

---

3️⃣ Rabin-Karp 알고리즘 (해싱 기반) - O(N) (평균)

Rabin-Karp 알고리즘은 해싱을 활용하여 needle과 haystack의 해시값을 비교하는 방식입니다.

export function strStrRK(haystack: string, needle: string): number {
  const base = 31;
  const mod = 1_000_000_007;
  const m = needle.length;
  const n = haystack.length;

  if (m > n) return -1;

  // 해시 값 계산
  let hashNeedle = 0;
  let hashHaystack = 0;
  let power = 1;

  for (let i = 0; i < m; i++) {
    hashNeedle = (hashNeedle * base + needle.charCodeAt(i)) % mod;
    hashHaystack = (hashHaystack * base + haystack.charCodeAt(i)) % mod;
    if (i > 0) power = (power * base) % mod;
  }

  // 롤링 해시 적용
  for (let i = 0; i <= n - m; i++) {
    if (hashHaystack === hashNeedle) {
      if (haystack.substring(i, i + m) === needle) return i;
    }
    if (i < n - m) {
      hashHaystack =
        (hashHaystack - haystack.charCodeAt(i) * power) % mod;
      hashHaystack = (hashHaystack * base + haystack.charCodeAt(i + m)) % mod;
      if (hashHaystack < 0) hashHaystack += mod;
    }
  }

  return -1;
}

✅ 장점: 평균 O(N), 문자열이 매우 길어도 빠르게 탐색
❌ 단점: 해시 충돌 가능성 (O(NM)의 최악 케이스)

---

4️⃣ Boyer-Moore 알고리즘 (문자열 검색 최적화)

Boyer-Moore 알고리즘은 뒤에서부터 탐색하여 불필요한 비교를 줄이는 방식입니다.
TypeScript에서는 indexOf를 활용하면 내부적으로 최적화된 검색이 이루어집니다.

---

🎯 결론 및 비교

알고리즘	시간 복잡도	장점	단점
Brute Force	O(N*M)	간단한 코드	긴 문자열에서 비효율적
KMP	O(N+M)	중복 비교 없음	LPS 배열 생성 필요
Rabin-Karp	O(N) (평균)	빠른 해싱	해시 충돌 가능
Boyer-Moore	O(N/M) (최적)	가장 빠를 수 있음	복잡한 구현

• 간단한 해결법: Brute Force
• 최적화 필요: KMP 또는 Rabin-Karp
• 고급 최적화: Boyer-Moore

---

📝 마무리

이 글에서는 LeetCode 28번 문제를 해결하는 다양한 방법을 소개했습니다.
코드를 직접 실행하면서 어떤 방식이 가장 효과적인지 테스트해보세요! 🚀

질문이나 의견은 댓글로 남겨주세요! 😊