[백준 BOJ] 1543번 문서 검색 (C++/cpp)

문제 설명

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

 

 

접근 방법 - 문자열을 활용한 브루트포스 알고리즘 문제

백준의 1543번 문제는 문자열에 있어 모든 경우의 수를 감안해 가며 해결해야 하는 문제이다.

해당 문제는, 영어로 이루어진 문서에 있어 특정 단어를 찾을 때 중복되지 않게 등장하는 총횟수를 구하여 출력해야 하는 문제이다.

 

시간제한이 2초나 되어서, 필자는 편안한 마음(...)으로 모든 부분 문자열을 검색해 나가며 정답을 구해보았다.

C++을 주로 활용하는 필자는, 여기서 제공하는 문자열 슬라이싱 함수 substr()을 주로 활용해 가면서 코드를 작성해 나갔다. 

이때, 몇몇 예제 입력들을 살펴보면 입력으로 주어지는 문서와 검색 단어가 공백을 포함할 수도 있기 때문에, 이 점을 고려하면서 입력을 받아야 문제가 없을 것이다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 자세한 설명과 코드를 아래에 기재해 놓으니 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 문서(st)와 검색할 단어(search)를 순차적으로 입력받는다.

이때, 공백을 포함한 입력이 들어올 수도 있기 때문에 필자는 C++ 기준으로 getline()을 통해 입력을 받게끔 하였다.

 

2) st에서 search가 등장한 총횟수를 저장할 변수 result를 0으로 초기화하여 선언해 둔다. 

(코드의 간결성을 위하여, 필자는 search의 길이를 size로 따로 저장해두기도 하였다.)

 

3) st의 길이만큼, 반복문을 수행하여 아래의 연산을 취한다.

(이때, i는 각 부분 문자열의 시작 위치로 활용할 예정이다.)

- st에 대하여, i번부터 시작하여 길이가 size만큼인 부분 문자열을 추출하고, 이를 임의의 변수 test에 저장한다.

- 위에서 추출한 test와 search가 동일한지를 판별한다.

만약 같은 값을 가진다면, result에 1을 추가한다. 그리고 st에 있어 test가 나타난 곳의 바로 다음 위치부터 다시 검색할 수 있도록 i에 size를 더하도록 한다.

다만 서로 다른 값을 가진다면, 바로 다음 위치의 부분 문자열을 탐색하기 위해 i에 1을 더하고 연산을 이어가도록 한다.

 

4) 위 연산이 모두 완료되었다면, 최종적으로 저장된 result의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <string>
#define endl '\n'
using namespace std;

//백준 1543번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	string st, search;
	getline(cin, st);
	getline(cin, search);

	int size = search.length();
	int result = 0;
	for (int i = 0; i < st.length(); ) {
		string test = st.substr(i, size);
		if (search == test) {
			result++;
			i += size;
		}
		else {
			i++;
		}
	}

	cout << result << endl;
}

 

제출 결과

(2022.12.10 백준 1543번 문제 제출 결과)

작동 구조는 동일하지만, 옛날 코드는 너무 지저분해서 다시 정리해서 업로드를 하였다.