[C++] 백준 온라인 저지 1543번 문서 검색 풀이

문서에서 어떤 단어를 최대 몇 번 검색할 수 있는지 알아내는 문제

 

---

문제의 조건

 

세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다.

세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어진다. 이 길이는 최대 50이다. 문서와 단어는 알파벳 소문자와 공백으로 이루어져 있다.

 

출력

첫째 줄에 중복되지 않게 최대 몇 번 등장하는지 출력한다.

 

 

풀이 과정

 

 입력으로 주어지는 문서가 공백을 포함하기 때문에 일반적인 cin으로는 입력받을 수 없고(공백 나오면 입력을 중단함) 한 줄 단위로 입력받아야 합니다. 이 때 사용할 수 있는 것이 getline 함수인데 저는 string을 사용했기 때문에 string에 있는 getline 함수를 사용했습니다. 

 

https://jhnyang.tistory.com/107

C언어 문자열 istream::getline()과 C++ string의 getline()! 한 줄 읽는 함수가 두 개?

 

 자세한 사용법은 위 블로그를 참고하시면 좋습니다. 

 

 입력을 받은 후 검색하고 싶은 단어의 길이만큼 문서에서 복사합니다. 검색하고 싶은 단어와 복사한 단어가 같으면 정답 카운트를 증가시키고 반복자를 검색하고 싶은 단어의 길이만큼 뒤로 보냅니다. 같지 않으면 다음 문자로 넘어가서 앞 과정을 반복합니다. 

 그리고 불필요한 연산을 줄여주려고 마지막에 남은 문자의 길이가 검색하고 싶은 단어의 길이보다 짧으면 반복문을 종료시켰습니다. 

 

 

코드

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main()
{
    string document, word;
    getline(cin, document); //한 줄 단위로 입력받는다.
    getline(cin, word);
    
    int answer = 0;
    for (int i = 0; document.length() > i; i++)
    {
        //남은 문자의 갯수가 word 길이보다 적으면 중단 
        if (word.length() > document.length() - i)
            break;
        
        //i번째 위치부터 word의 길이만큼 복사
        string tmp = document.substr(i, word.length());
        if (tmp == word)
        {
            //같으면 정답 카운트 증가
            answer++;
            //다음 반복을 하기 위해 조건을 확인하러 갔을 때 i++ 하기 때문에 여기서는 1을 뺀 만큼 증가시킴
            i += word.length() - 1;
        }
    }
    
    cout << answer;
    
    return 0;
}