문제 설명
여러분은 문자열 S에서 특정 문자열 P가 몇 번 나타나는지를 찾아야 합니다. 문자열 P는 문자열 S에 여러 번 나타날 수 있으며, 겹치는 경우도 있을 수 있습니다. 주어진 문자열 S의 길이는 1 이상 100,000 이하이며, 문자열 P의 길이는 1 이상 100 이하입니다. 대소문자는 구별하지 않습니다.
입력 형식
- 첫 번째 줄: 문자열 S (1 ≤ |S| ≤ 100,000)
- 두 번째 줄: 문자열 P (1 ≤ |P| ≤ 100)
출력 형식
모든 발생의 수를 정수로 출력하세요.
예제
입력
abCabcABCabc
abc
출력
4
문제 풀이 과정
1. 문제 이해하기
이 문제는 주어진 문자열 S에서 문자열 P가 몇 번 등장하는지를 확인하는 것입니다. 문자열이 대소문자를 구분하지 않기 때문에, 문제를 해결하기 위해 두 문자열 모두 소문자로 변환하여 비교해야 합니다.
2. 접근 방법
문자열 검색 문제는 여러 접근 방법이 있지만, 우리는 간단한 반복문을 사용하여 직접적으로 해결해 보겠습니다. 다음과 같은 절차로 문제를 해결할 것입니다:
- 문자열 S를 소문자로 변환합니다.
- 문자열 P를 소문자로 변환합니다.
- 반복문을 통해 문자열 S에서 문자열 P를 찾습니다.
- 각 발생 시 카운트를 증가시킵니다.
3. 알고리즘 설계
알고리즘의 복잡도는 O(n*m)입니다. 여기서 n은 문자열 S의 길이, m은 문자열 P의 길이입니다. 두 문자열을 직접 비교하기 때문에, 최악의 경우 모든 인덱스에서 문자열 P를 탐색해야 할 수 있습니다.
4. C# 코드 구현
아래는 C# 코드 예시입니다.
using System;
class Program
{
static void Main(string[] args)
{
string S = Console.ReadLine();
string P = Console.ReadLine();
// 대소문자를 구분하지 않기 위해 소문자로 변환
S = S.ToLower();
P = P.ToLower();
int count = 0;
int position = 0;
while ((position = S.IndexOf(P, position)) != -1)
{
count++;
position++; // 겹치는 경우를 고려하여 위치를 한 칸 이동
}
Console.WriteLine(count);
}
}
5. 코드 설명
코드는 다음과 같은 단계를 포함합니다:
- 사용자로부터 문자열 S와 P를 입력받습니다.
- 문자열 S와 P를 소문자로 변환하여 비교를 용이하게 합니다.
- while 루프를 통해 문자열 S에서 P의 위치를 찾습니다.
- S.IndexOf() 메서드를 사용하여 현재 위치부터 P의 위치를 찾습니다. 찾은 위치가 -1이 아닌 경우, 카운트를 증가시키고 다음 위치로 이동합니다.
- 모든 발생 수를 출력합니다.
성능 고려사항
이 코드의 시간 복잡도는 O(n*m)이며, 이는 문자열 S의 길이와 P의 길이에 따라 달라집니다. 만약 S의 길이가 100,000이고 P의 길이가 100이라면, 최악의 경우 10,000,000 연산이 요구될 수 있습니다. 이는 다소 비효율적일 수 있습니다.
따라서, 만약 성능을 더욱 개선하고 싶다면 KMP(Knuth-Morris-Pratt) 알고리즘과 같은 문자열 검색 알고리즘을 고려해볼 수 있습니다. KMP 알고리즘은 O(n + m)의 시간 복잡도를 가지며, 더 효율적인 검색을 가능하게 합니다.
5-1. KMP 알고리즘 개요
KMP 알고리즘은 부분 문자열 검색을 위한 효율적인 방법입니다. 이 알고리즘은 아래와 같은 원리를 이용합니다:
- 먼저, 패턴 문자열 P의 부분 일치를 저장하는 배열을 생성합니다.
- 문자열 S를 탐색하면서, 만약 불일치가 발생했을 때 패턴 문자열에서 몇 개의 문자를 건너뛸 수 있는지를 계산합니다.
5-2. KMP 알고리즘 C# 구현
아래는 KMP 알고리즘을 구현한 C# 코드입니다.
using System;
class Program
{
static void Main(string[] args)
{
string S = Console.ReadLine();
string P = Console.ReadLine();
// 대소문자를 구분하지 않기 위해 소문자로 변환
S = S.ToLower();
P = P.ToLower();
int count = KMP(S, P);
Console.WriteLine(count);
}
static int KMP(string S, string P)
{
int m = P.Length;
int n = S.Length;
int count = 0;
// LPS 배열 초기화
int[] lps = new int[m];
ComputeLPSArray(P, m, lps);
int i = 0; // S의 인덱스
int j = 0; // P의 인덱스
while (i < n)
{
if (P[j] == S[i])
{
i++;
j++;
}
if (j == m)
{
count++;
j = lps[j - 1];
}
else if (i < n && P[j] != S[i])
{
if (j != 0)
j = lps[j - 1];
else
i++;
}
}
return count;
}
static void ComputeLPSArray(string P, int m, int[] lps)
{
int len = 0;
int i = 1;
lps[0] = 0;
while (i < m)
{
if (P[i] == P[len])
{
len++;
lps[i] = len;
i++;
}
else
{
if (len != 0)
len = lps[len - 1];
else
{
lps[i] = 0;
i++;
}
}
}
}
}
6. KMP 알고리즘 코드 설명
위 코드는 다음과 같은 절차로 작동합니다:
- 우선 문자열 S와 P를 소문자로 변환합니다. 이를 통해 대소문자 구분을 없앱니다.
- KMP 메서드를 호출하여 문자열 P가 문자열 S에 몇 번 나타나는지를 탐색합니다.
- KMP 메서드 내부에서 LPS 배열을 생성합니다. LPS 배열은 패턴 P의 접두사와 접미사의 최대 길이를 저장합니다.
- 문자열 S를 스캔하면서 패턴 P의 매칭을 진행합니다. 매칭이 성공하면 카운트를 증가시키고, 매칭이 실패하면 LPS 배열을 참조하여 위치를 조정합니다.
결론
이번 강좌에서는 C#을 이용하여 문자열에서 특정 문자열을 찾는 문제를 해결하는 방법에 대해 알아보았습니다. 간단한 반복문을 이용한 접근부터 KMP 알고리즘으로의 확장까지, 문자열 검색 문제에 대한 기본 개념과 효율적인 접근 방법을 학습할 수 있었습니다. 이 문제를 해결하는 과정에서 다양한 코드 구현 방식과 알고리즘의 복잡도를 이해하는 데 도움이 되었기를 바랍니다.