백준 11008번 복붙의 달인

문제 링크입니다: https://www.acmicpc.net/problem/11008

단순 브루트 포스(Brute Force) 문제였습니다.

KMP 알고리즘을 적용할까도 생각을 했지만 굳이 그럴 필요가 없었기 때문에 KMP 알고리즘을 이용하진 않았습니다.

알고리즘은 아래와 같습니다.

1. s 문자열의 처음부터 끝까지 반복문을 돌립니다.

2. s 문자열을 탐색하는 도중 부분문자열이 p와 같을 때 인덱스를 p만큼 건너뛰고 시간을 업데이트해줍니다.

3. 반복문이 끝나면 업데이트 된 시간을 출력합니다.

#include <iostream>

#include <string>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        int test_case;

        cin >> test_case;

 

        for (int t = 0; t < test_case; t++)

        {

                 string s, p;

                 cin >> s >> p;

 

                 int second = s.length();

                 int idx = 0;

 

                 while (idx < s.length() - p.length() + 1)

                 {

                         //p의 첫 글자와 일치

                         if (s[idx] == p[0])

                         {

                                 bool same = true;

                                 for (int i = 0; i < p.length(); i++)

                                 {

                                          if (s[idx + i] != p[i])

                                          {

                                                  same = false;

                                                  break;

                                          }

                                 }

 

                                 //s의 부분문자열이 p와 모두 일치한다면

                                 if (same)

                                 {

                                          //그만큼 건너뛰고

                                          idx += p.length();

                                          //복사하므로 1초만 걸린다

                                          second -= (p.length() - 1);

                                          continue;

                                 }

                         }

                         idx++;

                 }

                 cout << second << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~