[백준] 1120: 문자열

문제

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

1. A의 앞에 아무 알파벳이나 추가한다.
2. A의 뒤에 아무 알파벳이나 추가한다.

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

입력

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

입력 예

adaabc aababbc

출력

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

출력 예

2

풀이

x, y = input().split()

mismatch_arr = []
for i in range(len(y)-len(x)+1):
    mismatch = 0
    start = i
    end = len(x)+i
    new_y = y[start:end]
    for j in range(len(x)):
        if x[j]!=new_y[j]:
            mismatch+=1
    mismatch_arr.append(mismatch)

result = min(mismatch_arr)

print(result)

항상 앞, 뒤로 문자가 추가되기 때문에 y의 연속되는 일부분 중에 x와 가장 차이가 적은 부분을 찾아서 x와 짝지어주고 y의 나머지에 해당하는 부분을 x의 앞뒤로 추가해주면 된다. 따라서 더이상의 차이는 발생하지 않는다.

예제로 살펴보면,

1)

adaabc
aababbc
=> 차이: 3

2)

 adaabc
aababbc
=> 차이: 2

따라서 2번에서 맨 앞에 a를 추가해주면 되기 때문에 최종 차이는 2이다.

+) 다른 풀이를 살펴보니 X[j] != Y[i+j]로 하여 더 간단해보였다.