[BOJ][C#] 2195 문자열 복사

📕 문제

📌 링크

📗 접근 방식

p의 첫 번째 문자와 s의 첫 번째 문자를 비교

• 일치하지 않는 경우, p의 다음 문자와 s의 첫 번째 문자를 비교
• 일치하지 않는 경우, p의 다음 문자와 s의 두 번째 문자를 비교

이러한 비교를 계속 진행하여 일치하는 부분 문자열을 찾는다.

이후 일치한 부분 문자열의 마지막 다음 위치부터 다시 비교를 시작
이 과정을 반복하여 최소한의 비교로 일치시킨 answer을 출력하면 된다.

📘 코드

namespace BOJ_2195
{
    class Program
    {
        static void Main()
        {
            string s = Console.ReadLine();
            string p = Console.ReadLine();

            int answer = 0;

            for(int i = 0 ; i < p.Length ;)
            {
                int maxLength = 0;
                for(int j = 0 ; j < s.Length ; j++)
                {
                    int temp = 0;
                    while(j + temp<s.Length && i + temp < p.Length && s[j + temp] == p[i + temp])
                    {
                        temp++;
                    }
                    maxLength = Math.Max(maxLength, temp);
                }

                i += maxLength;
                answer++;
            }

            Console.WriteLine(answer);
        }
    }
}

📙 오답노트

📒 알고리즘 분류

• 그리디 알고리즘
• 문자열