[백준 12780] 원피스

문제출처: https://www.acmicpc.net/problem/12780

문제

바야흐로 지금은 대해적 시대, 밀짚모자 해적단의 선장 교정이는 어린 시절 우연히 잊지 못할 한 마디를 들었다. 그것은 바로 해적 왕 골.D.상윤이 자신이 모은 모든 보물인 원피스를 위대한 항로에 놓고 왔다는 것이었다. 원피스를 가진 자는 이 세상을 가질 수 있다는 매혹적인 얘기였다.

모두들 말도 안 된다고 고개를 저었지만 교정이는 동료를 모아 원피스를 찾아 여행을 떠났다. 하늘섬을 지나 어인섬도 지나고 사황을 무너뜨린 뒤 교정이와 동료들은 결국 원피스의 위치가 적힌 결정적인 단서를 찾아냈다. 이 단서는 한 눈에 봐서는 해독이 어려웠다. 왜냐하면 여기에는 그저 알파벳 대문자들이 연속해서 적혀있었기 때문이다.

하지만 천재적인 두뇌를 가진 교정이의 동료이자 해적단의 항해사 진아는 단번에 이 단서에 어떤 특정 문자열이 여러 번 등장한다는 것을 직감했다.

이 특정 문자열이 어떤 문자열인지는 잘 알 수 없었던 진아는 자신이 생각한 모든 문자열이 이 단서에서 총 몇 번 등장하는지 알아보기로 했다. 아마도 가장 많이 등장한 문자열이 원피스의 위치를 알려줄 것이라고 생각했기 때문이다.

진아는 밀짚모자 해적단의 프로그래밍 담당인 당신에게 도움을 요청했다. 단서 전체에 진아가 원하는 문자열이 몇 번 등장하는지 알아내는 프로그램을 작성하라.

입력

입력의 첫 줄에는 해적단이 획득한 단서의 문자열 H가 주어진다.(0 < |H| ≤ 100,000)

입력의 두 번째 줄에는 진아가 H에서 등장 횟수를 알고 싶은 문자열 N이 주어진다.(0 < |N| ≤ 10)

단, N과 H는 공백 없는 문자열로 주어지며, 모두 알파벳 대문자로 이루어져 있다.

출력

H에서 N이 몇 번 등장하는지 출력한다.

풀이

이런 "A문자열에서 B문자열이 몇번나오냐?" 문제를 효율적으로 풀 수 있는 KMP알고리즘이있습니다. 

아래의 저의 풀이는 O(N*M)이지만, KMP알고리즘을이용한 풀이는 무려 O(N+M)입니다.. 그런데 아직 제가 KMP알고리즘을 몰라서 다음에 다시 이 방법으로 풀어보려합니다.(알고계시면 좋을 것 같아서..)

제 풀이 중 어려운 것은 없지만 A와 B를 비교 하기위해 12행의 조건식을 사용한것을 이해하셔야합니다.  이렇게 일일이 비교하는것입니다. 

그리고 19~22행은 B문자열이 A에없을 때 빠져나오는과정입니다. 28행에서 check가 true면 해당 문자열이 A에 있는것이므로 카운팅해줍니다.

코드

#include<iostream>
#include<string>
using namespace std;
int main()
{
	int t;
	string s, p;
		//횟수
		int cnt = 0;
		cin >> s >> p;
		//정확히 s.size()-p.size()+1번 비교함
		for (int i = 0; i<s.size() - p.size() + 1; i++)
		{
			//문자열이 있는지 확인하는 변수
			bool check = true;
			for (int j = 0; j < p.size(); j++)
			{
				//없으면
				if (s[i + j] != p[j])
				{
					check = false;
					break;
				}
			}
			//true면 B가 A에 존재하는거임.
			if (check)cnt++;
		}
		cout << cnt << endl;
}

결과