[백준] 그리디알고리즘 - 1543. 문서검색

문제

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

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

 

입력

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

 

출력

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

 

예제 입력1

ababababa
aba

 

예제 출력1

2

 

생각

왜 그리디 알고리즘으로 분류되어 있는지는 모르겠으나 그렇게 어려운 문제는 아니었다. 

다만, 미처 생각지도 못한 조건들이 몇가지 있었다. 

1. getline으로 받아줘야된다. 입력형식에서 공백이 들어갈 수 있다고 쓰여있다.

2. 단어가 문서보다 큰 경우를 처리해주지 않으면 런타임에러가 발생한다. 

3. 단어를 찾아서 증가시키고 난 후 i 인덱스를 단어만큼 증가시켜줘야되는데, i++되는 것을 감안해서 -1 시켜야한다. 

 

작성한 코드

#include <iostream>

using namespace std;
int cnt = 0;

int main(int argc, const char * argv[]) {
    // insert code here...
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    string d, w; //d:document w:word
    
    getline(cin, d); //공백이 들어갈 수 있으므로 getline으로 받아줘야한다.
    getline(cin, w);
    
    if(d.length() < w.length()){ // 단어가 문서보다 클 때는 0출력
        cout << 0 << "\n";
    }else{
        for(int i=0; i<=d.size()-w.size(); i++){
            bool check = true;
            
            for(int j=0; j<w.size(); j++){ //word가 있는지 체크
                //printf("%c %c : %d\n", d[i], w[j], cnt);
                if(d[i+j]!=w[j]){
                    check = false;
                    break;
                }
            }
            if(check){
                cnt ++;
                i += w.size()-1; // -1 해줘야한다!
            }
        }
        cout << cnt << "\n";
    }
}