[python] 백준 1543 : 문서 검색

[python] 백준 1543 : 문서 검색

1543번: 문서 검색 (acmicpc.net)

1543번: 문서 검색

실버 4

브루트포스, 그리디, 문자열

---

접근

예제 입력1을 예시로 접근해보자.

ababababa
aba

첫줄에 입력한 글자를 인덱스 0부터 끝까지 탐색할 필요가 없다.

aba라는 3글자가 첫줄에 입력한 문자열에 존재하는지 확인하는 것이기 때문에 맨 처음 인덱스부터 맨 끝에서 세번째 인덱스까지 탐색하면 된다. 따라서 for i in range(len(문자열변수) - len(찾을 문자열 변수) + 1)로 범위를 잡을 수 있다.

처음에 0~2번 인덱스에 aba가 있음을 알았다면, 중복을 피하기 위해 다음 탐색은 3번 인덱스부터 이어지도록 만들어야 한다. 변수 하나를 더 만들어서 문자열이 일치할 때 마다 중복 범위를 벗어나는 위치의 인덱스 값을 할당받는 역할을 하게끔 한다.

 

코드

import sys; input = sys.stdin.readline
document = input().rstrip()
search = input().rstrip()
cnt = 0
idx = 0
for i in range(len(document) - len(search)+1):
    for j in range(len(search)):
        if document[i+j] != search[j] or i<idx:
            break
    else:
        cnt += 1
        idx = i+len(search)
print(cnt)

for~else문을 이용해 글자가 완전히 일치할 경우 else문을 실행하도록 한다.

idx라는 변수는 document를 탐색하는 인덱스 i에 찾는 문자열 search의 길이만큼을 더해준 값을 할당한다.

 

ababababa 에서 가장 먼저 찾아지는 aba는 0~2번 인덱스에 위치해 있다.

aba를 셈할때 중복을 피해야하므로, 0~2번 인덱스에 대한 탐색을 건너뛰고 3번 인덱스로 넘어가도록 만들어야 한다.

외부 반복문에서 현재 i 값이 0이기 때문에, idx를 i+len(search) 값으로 할당해주면 i가 3번 인덱스에 도달하지 않았을 경우 continue를 만나 i값을 바로 증가시키게 만든다.

i가 3이 되면 다시 탐색을 시도하고 글자가 같다면 idx값이 또 중복 범위를 피할 수 있도록 다음 인덱스 값을 할당한다.

 

아이디어를 떠올리기는 쉬운편이었는데 구현할 때 인덱스 문제가 자꾸 생겨 애를 먹었다.

 

아래는 파이썬의 슬라이싱 기법을 활용한 풀이법이다.

코드2

import sys; input = sys.stdin.readline
document = input().rstrip()
search = input().rstrip()
cnt = 0
idx = 0
for i in range(len(document) - len(search)+1):
    if idx > i:
        continue
    if search == document[i: i+len(search)]:
        cnt += 1
        idx = i+len(search)
print(cnt)

 

if search == document[i: i+len(search)]

i값을 기준으로 찾으려는 글자의 길이만큼의 값을 document 문자열에서 가져오고 이를 search와 비교하는 방법이다.

슬라이싱 기법을 이해하고 있다면 이게 더 눈에 잘 들어오는 풀이가 될 것 같다.