[그리디/브루트포스] 백준 1543 문서 검색 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1543번: 문서 검색

 

 

 

2. 문제 풀이

 문서 내에 몇 개의 단어가 포함되어있는지 찾는 문제입니다. 단, 중복은 안됩니다.

 

문서: aaaa
단어: aa

출력: 2

 예를 들어, 위 예시에서는 aa가 총 2개 있습니다.

aaaa aaaa aaaa 이렇게 중복해서 찾으면 안됩니다.

 

 

 

3. 코드

doc = input()  # 문서
word = input()  # 단어

cnt = 0  # 등장 횟수
idx = 0  # 단어의 몇 번째 글자
n = len(word)-1  # 단어의 마지막 인덱스
for s in doc:
    # 철자가 같고 마지막 글자가 아니면 idx를 1개 늘림
    if s == word[idx]:
        if idx < n:
            idx += 1

        # 철자가 같고 마지막 글자이면, 검색 완료
        else:
            idx = 0
            cnt += 1

    # 철자가 다르면, 다시 처음부터 철자검색
    else:
        idx = 0
print(cnt)

 맨 처음에는 1개씩 매칭하면서 틀리면 처음부터 다시 비교했습니다. 예제 입력은 모두 통과했지만, 아래와 같은 반례가 있습니다.

 

ababc
abc

출력: 0
정답: 1

 idx가 2일 때, c가 아니라고 바로 넘어가면 안됩니다. 그러면 뒤에 abc를 못 찾게 됩니다. 따라서 단어 매칭이 안될 경우, 단어 길이만큼 스킵하는 게 아니라 1칸만 옮겨야 합니다.

 

 

doc = input().rstrip()  # 문서
word = input().rstrip()  # 단어

cnt = 0  # 등장 횟수
idx = 0  # 문서의 철자 인덱스
while True:
    # 문서의 길이를 넘어서면, 탐색 종료
    if idx + len(word) > len(doc):
        break

    for i in range(len(word)):
        # 중간에 맞지 않으면 끊기
        if doc[idx+i] != word[i]:
            idx += 1
            break

    # 중간에 안 끊어졌으면 단어 1개 탐색 완료
    else:
        cnt += 1
        idx += len(word)
print(cnt)

 문서 내에서 1글자씩 이동하며, 단어가 있는지 탐색합니다. 단어를 찾으면, 그제서야 단어 길이만큼 이동합니다.