브루트포스의 기본은 슬라이딩 윈도우(sliding window)

1. 문제

 

1120번: 문자열 (acmicpc.net)

1120번: 문자열

 

2. 풀이

 

생각보다 어렵다...

 

첫번째 문자열에 앞에 알파벳 넣어보고... 혹은 뒤에 알파벳 넣어보고...

 

두번째 문자열과 길이가 같아질때 비교해서 서로 다른 문자의 개수 세보고...

 

그러면 26개 알파벳 리스트 만들어서 중복조합으로 길이 차이만큼 뽑아서 앞 뒤로 넣어보고 비교해보나..??

 

두 문자열 길이의 차이가 k이면..

 

k개 모두 임의의 알파벳 26개 앞에 넣어보고... 

 

k-1개 앞에 나머지 1개 뒤에

 

k-2개 앞에.. 나머지 2개 뒤에..

 

...

 

이렇게 하니까 시간안에 안나오고.. 중복조합이 시간이 너무 오래걸림

 

아니면 그리디적인 접근으로 가야하나??

 

두번째 문자열에서 하나씩 뽑아봐서 첫번째 문자열 앞 문자부터 비교해서 다르면 앞에 넣고.. 같으면 뒤에넣기 시작하고...

 

이렇게 하자니 koder, topcoder 얘가 최소 차이가 1개라는게 설명이 안됨..

 

...

 

조금만 생각해보면 의외로 간단하다

 

첫번째 문자열을 두번째 문자열 위에서 슬라이딩 윈도우로 모든 경우 비교해보면 된다

 

슬라이딩 윈도우(sliding window)가 뭔지는 딥러닝에서 배웠지

 

예를 들어 koder, topcoder을 생각해보면..

 

 

위와 같다

 

보라색 빈칸은 어떻게 처리하면 될까??

 

최소 차이를 구해야하므로.. 보라색 빈칸은 두번째 문자열에 대응하는 문자 그대로 가지고오면 최소 차이가 될 것이다

 

 

따라서 index 0번부터 두 문자열 길이의 차이까지 첫번째 문자열의 출발점으로 삼고

 

 

 

두번째 문자열 topcoder는 첫번째 문자열 길이만큼 slicing해가지고 첫번째 문자열과 비교해서 모든 차이를 구해보고

 

최소 차이를 구하면 될 것이다

 

from sys import stdin

a,b = stdin.readline().rstrip().split()

len_a = len(a)
len_b = len(b)

min_value = 51

for i in range(len_b-len_a+1):
    
    new_b = b[i:len_a+i]

    answer = 0

    for x,y in zip(a,new_b):
        
        if x != y:
            
            answer += 1
    
    if min_value > answer:
        
        min_value = answer

print(min_value)