Problem Solving/Online Judge
[BOJ] #1543 - 문서 검색
se0m
2021. 6. 15. 17:30
1543번: 문서 검색
세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한
www.acmicpc.net
** 문제 유형
- 순차 탐색
** 풀이
- 문서의 길이는 최대 2,500이고, 단어의 길이는 최대 50
- 시간 복잡도 O(NM)의 알고리즘으로 해결 가능
- 단순히 모든 경우의 수를 계산하여 문제 해결 가능
- 문서와 단어의 위치를 맞추어서 반복적으로 비교
# 방법 1
document = input()
word = input()
index = 0
result = 0
while len(document) - index >= len(word):
# 문서에서 보고 있는 단어가 찾고자 하는 단어인 경우
if document[index:index + len(word)] == word:
result += 1
index += len(word) # 문서의 단어와 일치하면, 단어의 길이만큼 이동
else:
index += 1
print(result)
# 방법 2
data = input()
search = input()
print(data.count(search))