[백준] 1543번 : 문서 검색

유형 : 정렬

[예제1]

ababababa
aba

[출력1]

2

[예제2]

a a a a a
a a

[출력2]

2

---

1. 내 풀이

text = input()
word = input()
print(text.count(word))

▷ count()로 전체 문서 중 원하는 단어가 몇 개인지 셀 수 있었다.

 

 

2. 다른 풀이

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online

** 핵심 아이디어
1. 문서의 길이는 최대 2500이고 단어의 길이는 최대 50이다.
2. 단순히 모든 경우의 수를 계산하여 문제를 해결할 수 있다.
3. 시간 복잡도 O(NM)의 알고리즘으로 해결할 수 있다.
- 문서, 단어 길이가 크지 않기 때문에 모든 경우를 파악해도 충분하다.

 

ex. 문서 : ababababa  단어 : aba

 

documnet = 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)

 

 

문제 출처 : https://www.acmicpc.net/problem/1543

1543번: 문서 검색