백준 1543번 <문서 검색>

백준 알고리즘 1543번

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

1543번: 문서 검색

---

1543번

문서에 단어가 총 몇 번 등장하는지 카운트하여 횟수를 출력한다.

이때 단어가 중복되지 않게 카운트하여야 한다.

즉 ababacabc 가 문서이고 단어가 aba일 때,

맨 앞에 ababa를 보면 2번을 셀 수 있지만 a가 중복되기 때문에 1번으로 카운트한다.

 

입력으로 첫 줄에 문서 document가 주어지고 둘째 줄에 검색할 단어 search가 주어진다.

 

출력으로는 단어가 문서에 중복되지 않게 몇 번 등장하는지 출력한다.

---

문제 해결

2가지 방법으로 풀었다.

처음 방법은 파이썬의 replace 함수를 이용하여 단어를 $로 바꾸어준 후 $의 개수를 세었다.

(replace 함수를 사용할 때는 

text = "asdf"
text = text.replace("a", "v")

이렇게 사용해야 함을 기억하자!!! text.replace()만 쓰면 바뀌지 않는다. )

 

import sys
input = sys.stdin.readline

document = input().rstrip()
search = input().rstrip()

document = document.replace(search, "$")

result = 0
for i in range(len(document)):
    if document[i] == "$":
        result += 1
print(result)

두 번째 방법은 replace()를 사용하지 않고 while 문을 이용하여 탐색하였다.

 

while 문으로 이용하여 document를 처음부터 본다. 이때 document의 부분을 보기 위해 dIdx를 사용하였다.

document의 길이 - dIdx가 len(search)보다 작으면 종료된다.

while 문 안에서는 if문으로 search와 document의 부분인 document[dIdx:dIdx+len(search)]를 비교하여 같으면 result에 1을 더해주고 dIdx에는 len(search)만큼 더해준다. document[dIdx:dIdx+len(search)]로 하면 dIdx 인덱스에서부터 len(search) 길이 만큼의 document의 부분을 얻을 수 있다. 이게 search와 같다는 것은 검색에 성공한 것으로 볼 수 있다.

만약 같지 않다면 dIdx에 1을 더하면 된다. (다음 인덱스로 나아가서 다시 비교를 해야 하니까)

---

코드

import sys
input = sys.stdin.readline

def check(document, search):
    dIdx = 0
    result = 0
    while(len(document)-dIdx >= len(search)):
        if document[dIdx:dIdx+len(search)] == search:
            result += 1
            dIdx += len(search)
        else:
            dIdx += 1
    return result

document = input().rstrip()
search = input().rstrip()
print(check(document, search))

---

결과

---