백준 1543 문서 검색 — C++ 풀이

📄 문서 검색 성공 — C++ 풀이

문제 설명

주어진 문서에서, 특정 단어가 몇 번 등장하는지 세는 프로그램을 만듭니다.
단, 등장할 때 겹치지 않도록 세야 합니다.
즉, 어떤 위치에서 단어를 한 번 찾으면, 그 단어의 길이만큼 건너뛴 뒤부터 다시 찾기 시작합니다.

예를 들어, 문서가 aaaaaaa이고, 단어가 aa라면:

• 0번 위치에서 aa 발견 → 건너뜀
• 2번 위치에서 aa 발견 → 건너뜀
• 4번 위치에서 aa 발견 → 건너뜀

총 3번 등장합니다.

아이디어

이 문제를 풀기 위해 두 가지 규칙을 세웠습니다.

1️⃣ 단어 길이만큼 확인 후 일치하면 단어 길이만큼 건너뛰기

현재 위치에서부터 단어의 길이만큼 문서의 문자열을 잘라서 비교합니다.
비교한 결과 완전히 일치하면 단어의 길이만큼 인덱스를 증가시킵니다.
이렇게 하면 겹치지 않고 찾을 수 있습니다.

2️⃣ 하나라도 다르면 한 칸만 전진

만약 현재 위치에서 단어가 일치하지 않으면, 문서의 인덱스를 한 칸만 이동합니다.
왜냐하면 아직 다음 위치에 단어가 있을 수도 있기 때문입니다.

전체 코드

#include <iostream>
#include <cstring>
using namespace std;

int main(void)
{
    char arr[2501];    // 문서 문자열
    char str[51];      // 검색할 단어
    int cnt = 0;       // 등장 횟수
    bool check = true; // 현재 위치에서 단어가 일치하는지 여부

    cin.getline(arr, 2501); // 문서 입력
    cin.getline(str, 51);   // 검색 단어 입력

    int arr_n = strlen(arr); // 문서 길이
    int str_n = strlen(str); // 단어 길이

    for (int i = 0; i <= arr_n - str_n;) // i가 문서 끝에 가까워지면 멈춤
    {
        check = true;

        // 현재 위치부터 단어 길이만큼 비교
        for (int j = 0; j < str_n; j++)
        {
            if (arr[i + j] != str[j])
            {
                check = false;
                break;
            }
        }

        if (check)
        {
            cnt++;
            i += str_n; // 단어 길이만큼 건너뛰기
        }
        else
        {
            i++; // 한 칸만 전진
        }
    }

    cout << cnt << endl;
    return 0;
}

부분 코드별 설명

📌 입력 부분

cin.getline(arr, 2501);
cin.getline(str, 51);

• 첫 줄에 문서를 입력받습니다. 최대 2500자이므로 배열 크기를 2501로 설정합니다.
• 둘째 줄에 검색할 단어를 입력받습니다. 최대 50자이므로 배열 크기를 51로 설정합니다.

📌 문자열 길이 구하기

int arr_n = strlen(arr);
int str_n = strlen(str);

• strlen 함수를 이용해 문서의 길이와 단어의 길이를 각각 구합니다.
• 왜냐하면 배열의 크기와 실제 문자열의 길이는 다르기 때문입니다.

📌 문서 탐색 루프

for (int i = 0; i <= arr_n - str_n;)

• 문서의 현재 위치 i를 기준으로 탐색합니다.
• i <= arr_n - str_n인 이유는, 단어 길이만큼 비교해야 하기 때문에 문서의 끝까지 갈 필요가 없습니다.

📌 단어 일치 여부 확인

for (int j = 0; j < str_n; j++)
{
    if (arr[i + j] != str[j])
    {
        check = false;
        break;
    }
}

• 문서의 현재 위치 i부터 단어의 길이만큼 문서와 단어를 비교합니다.
• 하나라도 다르면 check = false로 바꾸고, 더 이상 비교하지 않습니다.

📌 건너뛰기 또는 한 칸 전진

if (check)
{
    cnt++;
    i += str_n; // 단어 길이만큼 건너뛰기
}
else
{
    i++; // 한 칸 전진
}

• check == true이면 단어가 발견된 것이므로, 등장 횟수 cnt를 증가시키고 단어 길이만큼 i를 이동합니다.
• check == false이면 단어가 발견되지 않았으므로, 문서의 다음 글자를 보기 위해 i++ 합니다.

결과 출력

cout << cnt << endl;

최종적으로 등장 횟수를 출력합니다.

예제 실행

문서	단어	출력
abababa	aba	2
a a a a a	a a	2
ababababa	ababa	1
aaaaaaa	aa	3