[백준/Python] Silver IV #1120 문자열

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의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력

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

풀이

x, y = map(str,input().split())
lx = len(x)
ly = len(y)
res = 50

for i in range(ly-lx+1):
  cnt = 0
  for k in range(lx):
    if x[k] != y[i+k]:
      cnt += 1
  if cnt < res: res = cnt
print(res)

문자열 X와 Y가 주어지고, X의 길이는 Y보다 작거나 같다.
X의 길이가 Y와 같아질 때까지 X의 앞이나 뒤에 아무 알파벳을 추가할 수 있다.
X와 Y의 길이가 같으면서, X와 Y의 차이를 최소로 하게 했을 때, 그 차이를 출력해야 한다.

예시로 있는 adaabc aababbc를 보면 X의 길이는 6, Y의 길이는 7이다.
앞이나 뒤에 아무 알파벳을 추가할 수 있다고 했으니 *adaabc 혹은 adaabc* 를 만들 수 있다고 생각하면 된다.
Y인 [aababbc]를 [aababb] 혹은 [ababbc]로 만들어 X인 [adaabc]와 비교를 하면 된다.
그러므로 X와 Y의 차이만큼 Y를 이동시켜 비교하여 가장 최소가 되는 수를 구하면 된다