백준 16172번, 나는 친구가 적다 (Large) 풀이

문제

백준 16172번

풀이

번형된 문자열 $ S $를 입력 받고 0-9를 모두 제거합니다.

찾고자 하는 문자열 $ T $를 전처리한 문자열 $ S $에서 선형 탐색($ O(|S|) $)하여 찾아줍니다.

 

선형 탐색을 굳이 구현할 필요 없이 STL에서 stirng.find를 지원해주니 find의 반환값이 string::npos인지 확인만 해주면 됩니다.

 

 

다만 주의할 점은 $ S $에서 0-9를 제거할 때, $ S.erase $를 사용하면 최악의 경우 $ O(|S|^2) $으로 TLE가 날 수 있습니다. 이 때문에, 다른 변수를 만들어 전처리해야 합니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	string tmp, s;
	getline(cin, tmp);
	for (const auto &c : tmp) {
		if ('0' <= c && c <= '9') continue;
		s.push_back(c);
	}


	string t;
	cin.ignore();
	getline(cin, t);

	cout << (s.find(t) != string::npos);
}