백준 1120 : 문자열 ( Python )

문제 링크

📌 사용 알고리즘 : brute forcing

A,B 두개의 문자열이 주어집니다. 이때 문자열의 길이는 항상 B 가 크거나 같습니다.
이때 문자열 A 에 앞 또는 뒤에 문자 하나를 넣을 수 있습니다.

이때 A,B 두개의 문자중에 서로 다른 문자를 최소화하는 것이 구하고자 하는 것입니다.

어짜피 원하는 문자를 앞 뒤에 붙이면 되므로 A 문자열만 보면 됩니다.

• koder topcoder

위와 같은 입력이 주어지면 어떻게 판단할까요?
가장 긴 공통부분문자열인 oder 를 겹치게 보면서 $$koder 과 topcoder 처럼 만들어주면
k 단어 하나만 다르게 됩니다.

단어의 길이는 최대 50 이므로 가장 긴 공통문자열을 O(N^2) 에 충분히 구할 수 있습니다.

B 문자열에서 시작점을 정한 뒤에 A 문자열과 하나씩 비교해주면서 서로 다른 문자의 개수를 매번 세어주고 그 중의 최소값을 구하면 됩니다.

📌 코드

import sys,math
input=sys.stdin.readline
from functools import lru_cache
from collections import deque
LMI=lambda:list(map(int,input().split()))
LMS=lambda:list(map(str,input().split()))
MI=lambda:map(int,input().split())
I=lambda:int(input())
GI=lambda x:[ LMI() for _ in range(x) ]
GS=lambda x:[ LMS() for _ in range(x) ]
V=lambda x,y:[ [False]*y for _ in range(x) ]

A,B=map(str,input().split())

ans = int(1e9)
for i in range(len(B)-len(A)+1):
    value = 0
    for j in range(len(A)):
        if B[i+j] != A[j]:
            value+=1
    ans = min(ans , value)

print(ans)