Baekjoon 1543 문서 검색

Link https://www.acmicpc.net/problem/1543

소스결과 1988 KB / 0 ms

언어 C++ 17

출처 Baekjoon

분류 그리디 알고리즘, 문자열 처리, 탐색

 

설명

영어로만 이루어진 문서가 주어질 때 검색하고 싶은 단어가 중복되지 않게 몇번 등장하는지 알아보자.

 

문제의 난이도에 비해 정답률이 낮은게 의문이었다. 아마 원인은 String 클래스의 find 함수나 indexOf 함수를 이용하며 생기는 검색 속도 문제일꺼 같다.

이번 문제는 String 클래스의 find와 indexOf 함수를 합쳐놓은(?) 방식으로 풀었다.

 

알고리즘

1. 총 문자열과, 검색할 문자열을 입력 받는다.

2. 0번 인덱스부터 문자열을 비교한다.

 2-1. 현재 탐색하는 문자열의 위치와, 탐색할 문자의 0번 인덱스부터 비교한다.

3. 문자열이 일치할 경우, 출력값 + 1을 해주며, 다음 검색 위치를 문자열 길이만큼 옮긴다.

4. 출력

 

소스코드

#include <iostream>
#include <string>

using namespace std;

bool compare(string& input, string& word, int pos, int len) {

	for (int i = 0; i < len; i++)
		if (input[pos + i] != word[i])
			return false;
	return true;
}

int main()
{
	string input, word;

	getline(cin, input);
	getline(cin, word);

	cin >> input >> word;

	int inputLen = input.length();
	int wordLen = word.length();
	int res = 0;

	for (int i = 0; i <= inputLen - wordLen;) {
		if (input[i] == word[0]) {
			if (compare(input, word, i, wordLen)) {
				res++;
				i += wordLen;
			}
			else
				i++;
		}
		else
			i++;
	}

	cout << res;

	return 0;
}