BOJ - 문자열(1120)

실버4 : 그리디 문제이다.

풀이

단순한 문제이다. 앞뒤에 어떠한 문자를 넣을 수 있으니, 현재 가지고 있는 문자열만 가지고서 부분적으로 보았을 때, 가장 작은 차이를 가지고 있는 지점만 알면된다. 이후는 맞춰서 끼워넣으면 되니까.

Code

A, B = input().split()
 
min_diff = 100
for i in range(len(B) - len(A) + 1):
    diff = 0
    for j in range(len(A)):
        if A[j] != B[i + j]:
            diff += 1
    min_diff = min(min_diff, diff)
 
print(min_diff)

Reference

• 백준(1120번) - 문자열