문제 설명
주어진 문자열 text와 찾고자 하는 문자열 pattern이 있습니다.
이때 text 내에서 pattern이 가장 처음으로 나타나는 위치를
반환하는 함수를 작성하세요. 만약 pattern이 text 내에 존재하지 않는다면 -1을 반환합니다.
입력 예시
- text: “hello world”
- pattern: “world”
출력 예시
- 결과: 6 (문자열 “world”가 인덱스 6부터 시작함)
문제 해결 전략
이 문제를 해결하기 위해 우리는 문자열 내에서 특정 패턴이 존재하는지 확인하고,
존재한다면 그 시작 인덱스를 찾아야 합니다. 문자열 탐색은 다양한 알고리즘이 있지만,
이 강좌에서는 가장 기본적이고 직관적인 방법인 ‘브루트 포스(Brute Force)’ 방법과
좀 더 효율적인 ‘KMP(카라츠바-모리셀)’ 알고리즘을 사용하여 문제를 해결해보겠습니다.
먼저 브루트 포스 방법을 살펴보겠습니다.
브루트 포스 접근법
브루트 포스 방법은 주어진 문자열과 찾고자 하는 패턴의 모든 조합을 비교하는 방식입니다.
이 방법은 간단하고 이해하기 쉽지만, 최악의 경우 시간 복잡도가 O(n*m)입니다. 여기서 n은
텍스트의 길이, m은 패턴의 길이입니다.
알고리즘 단계
- 텍스트의 길이(n)와 패턴의 길이(m) 변수를 설정합니다.
- 텍스트의 시작 위치를 하나씩 증가시키면서, 현재 위치에서부터 패턴과 비교합니다.
- 모든 문자 비교가 일치하면, 현재 시작 인덱스를 반환합니다.
- 모든 문자를 비교하고 패턴이 발견되지 않으면 -1을 반환합니다.
자바스크립트 코드 구현
function findFirstOccurrence(text, pattern) {
const n = text.length;
const m = pattern.length;
for (let i = 0; i <= n - m; i++) {
let j;
for (j = 0; j < m; j++) {
if (text[i + j] !== pattern[j]) {
break;
}
}
if (j === m) {
return i; // 패턴이 발견된 경우
}
}
return -1; // 패턴이 존재하지 않음
}
// 테스트 예시
console.log(findFirstOccurrence("hello world", "world")); // 6
console.log(findFirstOccurrence("hello world", "abc")); // -1
KMP 알고리즘
브루트 포스 방법은 간단하지만 비효율적일 수 있습니다. KMP 알고리즘은
검색 중에 불필요한 재검사를 방지하여 성능을 개선합니다. KMP 알고리즘의 기본 개념은
‘패턴의 일부가 매칭될 때, 나머지 부분을 재사용’하는 것입니다.
KMP 알고리즘 원리
KMP 알고리즘은 ‘부분 일치 테이블(또는 실패 함수)’을 활용하여 문자열 검색을
최적화합니다. 이 테이블은 검색 중 캐시할 수 있는 정보를 제공합니다.
KMP 알고리즘은 시간 복잡도가 O(n + m)으로, 이렇게 향상된 성능을 보여주므로
큰 데이터셋에 대해서 유용합니다.
알고리즘 단계
- 패턴에 대한 부분 일치 테이블을 생성합니다.
- 텍스트와 패턴을 비교하면서 일치하지 않을 경우, 테이블을 참조하여
패턴의 위치를 지정합니다. - 일치할 때까지 반복하며, 최종적으로 인덱스를 반환합니다.
부분 일치 테이블 생성
부분 일치 테이블을 생성하는 알고리즘은 다음과 같습니다. 이 테이블은 이전까지
검사했던 문자열에서 동일한 접두사와 접미사를 기반으로 하여 다음 비교 시
인덱스를 조정하는 데 사용됩니다.
function buildKMPTable(pattern) {
const m = pattern.length;
const lps = new Array(m).fill(0);
let len = 0;
let i = 1;
while (i < m) {
if (pattern[i] === pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len !== 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
return lps;
}
KMP 알고리즘 코드 구현
function KMPSearch(text, pattern) {
const n = text.length;
const m = pattern.length;
const lps = buildKMPTable(pattern);
let i = 0; // 텍스트 인덱스
let j = 0; // 패턴 인덱스
while (i < n) {
if (pattern[j] === text[i]) {
i++;
j++;
}
if (j === m) {
return i - j; // 패턴을 찾음
} else if (i < n && pattern[j] !== text[i]) {
if (j !== 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
return -1; // 패턴을 찾지 못함
}
// 테스트 예시
console.log(KMPSearch("hello world", "world")); // 6
console.log(KMPSearch("hello world", "abc")); // -1
결론
이 강좌에서는 문자열 찾기 문제를 해결하기 위한 두 가지 알고리즘,
브루트 포스 방법과 KMP 알고리즘의 구현 방법을 살펴보았습니다.
브루트 포스 방법은 직관적이고 간단하지만, 큰 문자열을 검색할 때는 비효율적일 수 있습니다.
반면 KMP 알고리즘은 더욱 효율적으로 패턴을 검색할 수 있는 방법을 제공합니다.
실제 코딩 테스트에서는 이러한 다양한 알고리즘을 이해하고 적절하게 활용하는 것이 중요합니다.
문자열 찾기와 관련된 문제는 코딩 테스트에서 자주 출제되므로, 다양한 예제를 풀어보며
경험을 쌓는 것이 필요합니다. 앞으로도 다양한 알고리즘 문제를 학습하여
역량을 더욱 향상시켜보시기 바랍니다.