[python/파이썬] 백준 1543 문서 검색

[문제 출처]

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

1543번: 문서 검색

 

 

[문제 풀이]

 

❌소스 코드1 - 틀렸습니다

 

문서의 처음부터 탐색하며 단어의 첫 번째 문자와 일치하면 다음 문자를 비교하도록 포인터 값을 증가시켰다.

포인터값이 단어의 길이와 동일해지면 모든 문자가 일치하므로 cnt값을 증가시키도록 했다.

 

이 코드는 틀린 코드인데, 

만일

 

ababac

abac

라는 입력이 주어지면

 

아래 코드는 문서를 한 번만 살펴보므로

ababac 밑줄 친 abac는 찾아내지 못한다. 가운데에 위치한 ab는 앞에 틀린 단어에 포함되어 있기 때문이다.

#1543

doc = input()
word = input()

d = 0
w = 0
cnt = 0
for i in range(len(doc)):
  if doc[i] == word[w]:
    w += 1
  else:
    w = 0

  if w == len(word):
    cnt += 1
    w = 0

print(cnt)

 

❌소스 코드2 - 틀렸습니다

 

위 코드의 문제를 해결하기 위해서

문서의 0번부터 탐색, 1번부터 탐색, 2번부터 탐색,, 이런 식으로 코드를 작성했다.

만일 1번부터 탐색을 하다가 0번부터 탐색할 때 찾은 단어가 중복으로 카운트될 수 있기에 

단어를 찾았을 때, 가장 마지막 문자를 영어 알파벳이 아닌 숫자 1로 바꾸어 주었다.

하지만 이런 경우에도 예외가 발생한 것인지 틀렸습니다가 나왔다.

#1543

doc = list(input())
word = input()

cnt = 0
for i in range(len(doc)):
  w = 0
  for j in range(i,len(doc)):
    if doc[j] == word[w]:
      w += 1
    else:
      w = 0

    if w == len(word):
      cnt += 1
      doc[j] = '1'
      w = 0

print(cnt)

 

✅소스 코드3 - 맞았습니다!!

 

접근 방법을 약간 바꿔서, 

0번부터 탐색, 1번부터 탐색,... 방법은 유지하면서 좀 더 간단한 방식으로 작성된 코드이다.

i번부터 찾고자 하는 단어 길이만큼의 단어가 찾는 단어와 일치하면 중복되지 않게 하기 위해서 그다음부터 다시 찾는 방식이다.

만일 일치하지 않는다면 i+1번에서 다시 반복한다.

#1543

doc = input()
word = input()

cnt = 0

i = 0
while i <= len(doc)-len(word):
    if doc[i:i+len(word)] == word:
        cnt += 1
        i += len(word)
    else:
        i += 1

print(cnt)