백준 1543번 문서 검색

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

진짜 간단한 문자열 탐색 문제였습니다.(솔직히 왜 그리디 알고리즘으로 분류되었는지는 모르겠습니다)

하지만, string size()와 length()의 반환형이 unsigned int라는 점을 인지 못함과 동시에 문제에서 공백 또한 포함이라는 것을 읽지 못해 수도 없이 틀렸던 문제였습니다.

간단히 설명하자면 아래와 같습니다.

1. string size()와 length()의 반환형이 unsigned int이기 때문에 주어진 문자열의 크기보다 부분문자열의 크기가 클 경우 underflow가 발생하기 때문에 런타임 에러가 뜹니다.

2. 문자열에 공백도 포함될 수 있기 때문에 cin이 아닌 getline을 통해 문자열을 입력받아야합니다.

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

1. 주어진 문자열의 크기만큼 반복문을 돌립니다.

2. 부분문자열과 동일한 구간이 나오면 result++를 해주고 그만큼 건너뜁니다.(중복탐색 방지)

#include <iostream>

#include <string>

using namespace std;

 

string S, subS;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

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

        getline(cin, S);

        getline(cin, subS);

 

        if (subS.size() > S.size())

                 cout << 0 << "\n";

        else

        {

                 int result = 0;

                 for (int i = 0; i < S.size() - subS.size() + 1; i++)

                 {

                         bool same = true;

                         for (int j = 0; j < subS.size(); j++)

                                 if (S[i + j] != subS[j])

                                 {

                                          same = false;

                                          break;

                                 }

                         if (same)

                         {

                                 result++;

                                 i += subS.size() - 1;

                         }

                 }

                 cout << result << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

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