[Python/파이썬] 백준 1120번 문자열

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

코드

import sys
input = sys.stdin.readline

a, b = input().split()

answer = 50
for i in range(len(b)-len(a)+1):
    cnt = 0
    for j in range(len(a)):
        if a[j] != b[j+i]:
            cnt += 1
    answer = min(answer, cnt)
print(answer)

 

 

b에서 a와 가장 유사도가 높은 부분을 찾은 뒤에 나머지 남은 길이는 b와 같은 글자들로 채워넣으면 a와 b의 차이를 최소로 할 수 있다.

예를 들어, 문제의 예제 3인 `koder topcoder`를 예시로 보면

 

topcoder

     koder

 

topcoder에서 coder 부분을 koder와 비교했을 때 가장 차이가 작은 것을 알 수 있다. 그렇다면 koder의 앞에 top을 추가하기만 하면 a와 b의 차이를 최소로 할 수 있는 것이다. 

 

그러니까 여기서는 문자 추가하고 하는 건 별다른 제한이 없으니 이건 무조건 b랑 같게 추가한다고 하고, 처음에 주어진 a가 b와 가장 유사도가 높을 수 있는 부분을 찾으면 된다.