[탐색] BAEKJOON '1543'번 '문서 검색'문제 (C++/python)

문제 : www.acmicpc.net/problem/1543

1543번: 문서 검색

 

 

 

• 문제 해결 아이디어

    1.  처음부터 일치하는 단어를 찾기위해 순차적으로 탐색하고, 찾았다면 찾은 단어 다음부터 다시 탐색한다.

   

 

 

• python

 

document = input()
key = input()

start = 0
result = 0

while len(document) - start >= len(key):
    if document[start:start + len(key)] == key:
        result += 1
        start += len(key)
    else:
        start += 1

print(result)

 

 

• c++

 

#include "iostream"
#include "string"

using namespace std;

int result=0;
string input, key;


// size가 넘어간다면 -1
// 해당 부분의 문자열과 단어가 일치한다면 1
// 그렇지 않은 경우는 0
int check_same(int start){
    int count =0;
    
    if(start + key.size() > input.size())
        return -1;
    
    for(int i=0 ; i< key.size() ; i++){
        if(input.at(start+i) == key.at(i)) 
            count++;
    }
    
    if(count == key.size())
        return 1;
    
    return 0;
}



// 해당 단어를 찾은 경우에, 그 단어가 끝난 다음을 다시 시작으로
// 찾지 못한 경우엔, 다음 단어를 시작으로 탐색한다.
void search_key(int start){
    
    int check = check_same(start);
    if(check == -1){
        ;
    }
    else if(check == 1){
        result++;
        search_key(start + key.size());
    }
    else if(check == 0){
        search_key(start+1);
    }
}



int main(){
    
    getline(cin,input);                  // 공백을 포함하여 입력받기 위해 getline사용
    getline(cin,key);
    
    search_key(0);
    
    printf("%d\n",result);
    
    return 0;
}

 

※ getline

knowable.tistory.com/24 참고