백준 1120(문자열) - Python(파이썬)

1120번: 문자열

접근 방법

최소인 값은 A의 문자를 하나씩 비교하여서 남는 문자열이 있는 경우 B와 똑같은 값을 채우면 최소값이 된다.

B	a	a	b	a	b	b	c
첫번재 A	a	d	a	a	b	c	c 채우기
두번째 A	a 채우기	a	d	a	a	b	c

풀이방법
① for문으로 B의 시작점을 변경하여서 0부터 시작해서 len(B)-len(A)까지 루프문을 돌리기
② 시작점으로부터 B와 A를 A의 길이까지 문자열을 비교해서 최솟값을 계속 비교하기
③ 단, 비교하는 과정에서 앞서 구한 최솟값보다 커버리면 A와 B 비교를 그만두기

import sys
#A,B 입력 받기
A,B =sys.stdin.readline().split()
minresult=len(A)#최댓값으로 가정
for i in range(len(B)-len(A)+1):#B의 시작점 지정
    result=0
    #A와 문자열 비교
    for j in range(len(A)):
        if A[j]!=B[i+j]:
            result+=1
        #최솟값이 앞에 구한것보다 커지면 그만두기(시간을 줄이기 위해 추가)
        if result>minresult:
            break
    #앞에서 구한 최솟값과 현재 구한 최솟값 비교
    minresult=min(minresult,result)

print(minresult)