C# 코딩테스트 강좌, 문자열 찾기

문제 설명

여러분은 문자열 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. 접근 방법

문자열 검색 문제는 여러 접근 방법이 있지만, 우리는 간단한 반복문을 사용하여 직접적으로 해결해 보겠습니다. 다음과 같은 절차로 문제를 해결할 것입니다:

  1. 문자열 S를 소문자로 변환합니다.
  2. 문자열 P를 소문자로 변환합니다.
  3. 반복문을 통해 문자열 S에서 문자열 P를 찾습니다.
  4. 각 발생 시 카운트를 증가시킵니다.

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. 코드 설명

코드는 다음과 같은 단계를 포함합니다:

  1. 사용자로부터 문자열 S와 P를 입력받습니다.
  2. 문자열 S와 P를 소문자로 변환하여 비교를 용이하게 합니다.
  3. while 루프를 통해 문자열 S에서 P의 위치를 찾습니다.
  4. S.IndexOf() 메서드를 사용하여 현재 위치부터 P의 위치를 찾습니다. 찾은 위치가 -1이 아닌 경우, 카운트를 증가시키고 다음 위치로 이동합니다.
  5. 모든 발생 수를 출력합니다.

성능 고려사항

이 코드의 시간 복잡도는 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 알고리즘 코드 설명

위 코드는 다음과 같은 절차로 작동합니다:

  1. 우선 문자열 S와 P를 소문자로 변환합니다. 이를 통해 대소문자 구분을 없앱니다.
  2. KMP 메서드를 호출하여 문자열 P가 문자열 S에 몇 번 나타나는지를 탐색합니다.
  3. KMP 메서드 내부에서 LPS 배열을 생성합니다. LPS 배열은 패턴 P의 접두사와 접미사의 최대 길이를 저장합니다.
  4. 문자열 S를 스캔하면서 패턴 P의 매칭을 진행합니다. 매칭이 성공하면 카운트를 증가시키고, 매칭이 실패하면 LPS 배열을 참조하여 위치를 조정합니다.

결론

이번 강좌에서는 C#을 이용하여 문자열에서 특정 문자열을 찾는 문제를 해결하는 방법에 대해 알아보았습니다. 간단한 반복문을 이용한 접근부터 KMP 알고리즘으로의 확장까지, 문자열 검색 문제에 대한 기본 개념과 효율적인 접근 방법을 학습할 수 있었습니다. 이 문제를 해결하는 과정에서 다양한 코드 구현 방식과 알고리즘의 복잡도를 이해하는 데 도움이 되었기를 바랍니다.

참고 자료