[BaekJoon 16916번] 부분 문자열(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 
 

[문제 풀이 사이트]

 
 

16916번: 부분 문자열

 
 

[문제 설명]

 
 

문자열 S의 부분 문자열이란, 문자열의 연속된 일부를 의미한다.
예를 들어, "aek", "joo", "ekj"는 "baekjoon"의 부분 문자열이고, "bak", "p", "oone"는 부분 문자열이 아니다.
문자열 S와 P가 주어졌을 때, P가 S의 부분 문자열인지 아닌지 알아보자.
 

 

[입력]

 
 

첫째 줄에 문자열 S, 둘째 줄에 문자열 P가 주어진다. 두 문자열은 빈 문자열이 아니며, 길이는 100만을 넘지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

 
 

[출력]

 
 

P가 S의 부분 문자열이면 1, 아니면 0을 출력한다.

 
 

[입출력 예]

 
 

입력	출력
baekjoon aek	1
baekjoon bak	0
baekjoon joo	1
baekjoon oone	0
baekjoon online	0
baekjoon baekjoon	1

 
 

[문제 풀이]

 
 

백준에 브론즈 문제로 분류되어 있는 문제이지만 새로운 함수를 사용해봐서 머릿속에 기억할 겸 포스팅해보려고 한다.
 
문자열 S와 문자열 P가 주어졌을 때 문자열 S에 문자열 P가 포함되는지를 알아야한다.
딱 문제를 보자마자 생각난건 string의 find함수였지만 문자열의 최대 길이가 100만 이하였기 때문에 시간초과가 발생했다.
시간 복잡도를 O(N)으로 해결해야했다.
find 함수는 시간 복잡도가 O(NM)이다.
 
찾아보니 strstr 함수 또한 시간 복잡도가 O(NM)인데, GCC의 라이브러리 구현인 libstdc++에서는 O(N+M)의 시간 복잡도의 알고리즘으로 구현되어 있다고 한다.
그래서 strstr 함수를 사용하여 간단하게 통과를 할 수 있었다.
strstr 함수는 찾고자하는 문자열을 찾는다면 해당 위치의 포인터(char* 형)를 반환하고, 찾지 못하면 NULL을 반환한다.
 
그 외에도 문자열 탐색을 할 때 사용하는 알고리즘인 KMP 알고리즘도 있는데 이 알고리즘도 학습하여 포스팅하도록 하겠다.
 
 

[최종 코드]

 
 

[GitHub]

 
 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 
 

#include <bits/stdc++.h>
using namespace std;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    string str; cin >> str;
    string temp; cin >> temp;
    
    if(strstr(str.c_str(), temp.c_str()) != NULL) {
        cout << 1;
    } else {
        cout << 0;
    }
    return 0;
}