[BOJ 1543, Python 3] 문서 검색

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

1543번: 문서 검색

 

풀이

앞에서부터 단어가 있는지 확인하면서 답을 구하면 됩니다.

이게 왜 가능하냐면 만약 앞에 단어(A)가 있지만, 조금 뒤에 있는 단어(B)를 선택한다고 해봅시다.

그 후에 다음 단어(C)를 선택할 때, B를 선택했을 때 C가 선택 가능하다면 A를 선택하고 C를 선택할 수도 있다는 것입니다.

위와 같은 상황인 단어 A와 B. 그리고 다음 단어 D가 있다고 할 때, 단어 길이 때문에 B를 선택하면 D를 선택할 수 없고, A를 선택하면 D를 선택할 수 있는 상황이 존재할 수도 있습니다.

그러므로 무조건 먼저 단어가 나온 것을 세면 최적의 해가 됩니다.

 

코드는 단어를 발견하면 그 길이만큼 건너뛰고 다시 탐색하는 코드입니다.

 

코드

s = input()
k = input()
x, y = 0, len(k)
 
ans = 0
while y <= len(s):
    if k == s[x:y]:
        x += len(k)
        y += len(k)
        ans += 1
    else:
        x += 1
        y += 1
print(ans)