[Baekjoon] 1120번 : 문자열 (Python, 문자열)

[Baekjoon] 1120번 : 문자열 (Python, 문자열)

 

목차

 

 

 

 

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

1120번: 문자열

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 68ms / 코드 길이 208B

 

a는 b보다 무조건 작거나 같다.

즉, a의 길이를 기준으로 b를 앞에서부터 비교한다.

그 이유는 현재 a가 b보다 길이가 작을 때 아무 알파벳이나 앞뒤로 붙일 수 있다는 의미는 a와 b의 특정 구간만큼의 비교에서 가장 작은 곳을 기점으로 나머지부분을 b로 채울 수 있기 때문이다.

 

예제의 예를 보자

a = koder, b = topcoder

(koder)
(topco)der

 (koder)
t(opcod)er

   (koder)
to(pcode)r

     (koder)
top(coder)

 

여기서 () 구간의 차이가 가장 적은 곳을 기준으로 a의 앞뒤에 알파벳이 들어간다고 가정하면 된다.

 

a,b = input().split()
res = 51
for i in range(len(b)-len(a)+1):
    cnt = 0
    tb = b[i:i+len(a)]
    for j in range(len(a)):
        if a[j] != tb[j]:
            cnt += 1
    res = min(res, cnt)
print(res)