백준 - 1543번 문서 검색 python 문제풀이 [Hellfer]

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

1543번: 문서 검색

🔷 알고리즘 분류 - 문자열, 브루트포스 알고리즘

난이도 - 실버 5

브루트 포스(Brute Force) 알고리즘은 컴퓨터 과학에서 가장 기본적인 알고리즘 중 하나로, 가능한 모든 경우의 수를 전부 검사해 보는 방식을 말합니다.

이 알고리즘은 문제를 해결하기 위한 가장 단순한 방법으로, 문제의 크기가 작을 때나 정확한 답을 찾아야 할 때 유용합니다. 

 

그러나 경우의 수가 많아지면 시간이 많이 소요되는 단점이 있습니다.

파이썬에서 브루트 포스 알고리즘이 주로 사용되는 경우는 다음과 같습니다:

완전 탐색: 모든 경우의 수를 일일이 확인하는 방식입니다. 

 

예를 들어, 배열에서 특정 합을 가진 부분 배열을 찾는 문제가 있을 때, 모든 부분 배열을 만들어서 합을 확인해 볼 수 있습니다.

순열과 조합: 순열은 n개의 원소를 사용해서 순서를 고려하여 r개를 나열하는 것이고, 조합은 n개의 원소 중에서 순서를 고려하지 않고 r개를 선택하는 것입니다. 

 

파이썬의 itertools 모듈에는 이러한 순열과 조합을 쉽게 구현할 수 있는 함수가 있습니다.

재귀 함수: 브루트 포스 알고리즘을 구현할 때 재귀 함수를 많이 사용합니다. 

 

재귀 함수를 사용하면 문제를 더 작은 문제로 나누어 해결할 수 있습니다.

백트래킹: 모든 경우의 수 중에서 특정 조건을 만족하는 경우만을 검사하는 방식입니다. 

 

이는 브루트 포스 알고리즘의 효율을 높여주는 기법 중 하나입니다.

🔶문제 풀이 - 브루트포스를 이용한 풀이

# 사용자로부터 두 개의 문자열을 입력받는다.
x=input()
y=input()

# count는 문자열 x에서 탐색한 글자 수를, result는 문자열 y와 일치하는 부분 문자열의 수를 나타내는 변수다.
count=0
result=0

# 문자열 x의 전체 길이에서 이미 탐색한 글자 수를 뺀 값이 문자열 y의 길이 이상인 동안 반복한다.
# 즉, 문자열 x에서 아직 탐색하지 않은 부분이 문자열 y의 길이보다 짧아지면 반복을 종료한다.
while len(x)-count>=len(y):

    #열 x에서 아직 탐색하지 않은 부분이 문자열 y와 일치하는지 확인한다.
    # 문자열 x의 count번째 글자부터 count+len(y)번째 글자까지가 문자열 y와 일치하면,
    # 일치하는 부분 문자열의 수를 하나 증가시키고, 탐색한 글자 수를 문자열 y의 길이만큼 증가시킨다.
    if x[count:count+len(y)]==y:
        result+=1
        count+=len(y)
        
    # 문자열 x에서 아직 탐색하지 않은 부분이 문자열 y와 일치하지 않으면,
    # 탐색한 글자 수를 하나 증가시킨다.
    else:
        count+=1
        
# 일치하는 부분 문자열의 수를 출력한다.
print(result)

🔶 문제 이해하기

아래와 같은 입력값이 주어졌다고 가정해 보겠습니다.

 

ababababa
aba

 

 "ababababa"이고, 찾고자 하는 단어(y)가 "aba"인 경우를 예시로 들어보겠습니다.

초기에 count는 0이고 result는 0입니다.

1. 첫 번째 반복에서 x [count:count+len(y)]는 x [0:3]이므로 "aba"입니다.

 

이는 word와 같으므로 result를 1 증가시키고 count를 len(y)만큼 증가시킵니다. (count는 이제 3입니다.)

2. 두 번째 반복에서 x [count:count+len(y)]는 x [3:6]이므로 "aba"입니다.

 

이는 y와 같으므로 result를 1 증가시키고 count를 len(y)만큼 증가시킵니다. (count는 이제 6입니다.)

3. 세 번째 반복에서 x [count:count+len(y)]는 x [6:9]이므로 "aba"입니다.

 

그런데 문자열의 끝까지 확인하면 "aba"가 아니라 "aba"의 일부인 "ab"가 됩니다.

 

따라서 이 경우 word와 같지 않으므로 count를 1 증가시킵니다. (count는 이제 7입니다.)

4. 네 번째 반복에서 x [count:count+len(y)]는 x [7:10]이므로 "ba"입니다.

 

이는 y와 같지 않으므로 count를 1 증가시킵니다. (y는 이제 8입니다.)

이제 len(x) - y는 1이므로, word의 길이인 3보다 작아집니다. 

 

따라서 반복문을 종료하고, result를 출력합니다.

따라서 이 경우 "ababababa"에서 "aba"는 2번 등장하므로 출력 결과는 2가 됩니다.

 

아래와 같은 입력값이 주어졌다고 가정해 보겠습니다.

 

ababababa
ababa

 

 "ababababa"이고, 찾고자 하는 단어(y)가 "ababa"인 경우를 예시로 들어보겠습니다.

초기에 count는 0이고 result는 0입니다.

1. 첫 번째 반복에서 x [count:count+len(y)]는 x [0:5]이므로 "ababa"입니다.

 

이는 word와 같으므로 result를 1 증가시키고 count를 len(y)만큼 증가시킵니다. (count는 이제 5입니다.)

2. 두 번째 반복에서 x [count:count+len(y)]는 x [5:10]이므로 while 문의 조건을 만족하지 않습니다.

 

따라서 반복을 종료하고, result를 출력합니다.

 

따라서 이 경우 "ababababa"에서 "ababa"는 1번 등장하므로 출력 결과는 1이 됩니다.