[백준 1120] 문자열(Python)

https://www.acmicpc.net/problem/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의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

예제 입력 1

adaabc aababbc

예제 출력 1

2

풀이 설명

1. 이 문제는 문자열의 앞뒤에 어떤 문자를 삽입하던 상관이 없으니, b의 어느 위치에 a가 위치해야 가장 일치하는지만 보면 된다.

2. b의 인덱스 0부터 a를 비교하여 다른 문자의 개수를 찾고, a를 한칸씩 옆으로 밀면서 최소값을 찾아간다.

Python3 코드

a, b = input().split()
minCnt = 51

for i in range(len(b) - len(a) + 1):
    count = 0
    for j in range(len(a)):
        if b[j+i] != a[j]:
            count += 1
    if count < minCnt:
        minCnt = count
        
print(minCnt)