[백준]_1543번 : 문서 검색(파이썬 and C언어)

1543번: 문서 검색

문서에서 주어진 단어가 몇 번이나 포함되어 있는지 중복을 제외하고 세야 하는 문제이다. 예를 들어 ababababa의 문서가 주어지고 검색 단어가 aba라면 ababababa → ababababa 이므로 답은 2이다. 

---

전략

따라서 이 문제를 풀기 위해서는 입력받은 문자열을 하나씩 쪼개어 배열에 저장한 뒤 검색 단어의 존재 여부에 따라 검사의 위치를 이동시켜 주는 방법을 선택해야 한다. 이해를 돕기 위해 위의 예시를 다시 사용하겠다. 

 

1. 0 인덱스부터 시작해서 찾고자 하는 단어(aba)의 길이(3) 만큼 기존문자열(ababababa)에서 검색한다. 
2. 만약 일치하면 답으로 할당된 변수를 1 증가시키고 그다음 검사 인덱스는 1이 아닌 0(기존 위치) + 3(길이)로 옮겨준다.
3. 만약 하나의 문자라도 일치하지 않으면 다음 검사 인덱스를 1 증가시킨다.
4. 위의 과정을 계속 반복한다.

이제 위의 과정을 코드로 옮기면 끝이다.

---

시도 1(Python)

import sys
input = sys.stdin.readline

word = input().strip()
func = input().strip()

cnt = 0
i = 0
while i <= len(word)-len(func):
    if func == word[i:i + len(func)]:
        cnt += 1
        i += len(func)
    else:
        i += 1
print(cnt)

<해석>  

1. word와 func를 입력받는다. 이때 이 둘은 문자열이기 때문에 뒤에 strip()을 붙여줘야지 마지막에 포함되는 '\n'을 제거해 줄 수 있다.

 

2. cnt는 답으로 사용될 변수이고 i는 검사 시작 인덱스의 위치이다.

 

3. 연산 횟수를 줄이기 위해 인덱스(i)는 len(word) - len(func)까지만 해준다. 왜냐하면 더 이상 남은 문자열의 길이가 func의 길이보다 작으면 애초에 검사할 필요성이 더 이상 없기 때문이다.

 

4. word의 i번째 인덱스부터 i+len(func)-1 인덱스까지 func와 일치하면 답(cnt)을 1 증가시키고 다음 검사 인덱스를 len(func)만큼 움직여 준다.

 

5. 4번을 만족하지 않을 시 인덱스 위치를 바로 다음으로 1칸만 이동시켜 준다.

 

하지만 필자는 다른 고수분들은 어떻게 풀었나 궁금해서 구글을 뒤져봤다. 그러다가 이 풀이를 보고 충격을 먹었다 ㅋㅋ

'이 풀이'가 이해가 잘 안 되는 사람들을 위해 func에 대입된 값을 ', '로 치환시키고 생각해 보기 바란다.

 

시도 2(C언어)

#include <stdio.h>
#include <string.h>
int checkword(int i, int f, char* word, char* func) {
    int f_index = 0;
    for (int j = i; j < i + f; j++) {
        if (word[j] != func[f_index]) return 0;
        f_index++;
    }
    return 1;
}
int main() {
    char word[2501];
    char func[51];
    gets(word);
    gets(func);
    int w = strlen(word), f = strlen(func);
    int i = 0, cnt = 0;
    while (i <= w - f) {
        if (checkword(i, f, word, func)) {
            cnt++;
            i += f;
        }
        else i++;
    }
    printf("%d", cnt);
    return 0;
}

 논리는 파이썬이랑 똑같지만 여러모로 귀찮은하지만 빨랐죠? C..