백준 알고리즘
[백준/Python]1120_문자열
헝그리개발자
2021. 6. 14. 00:17
문제
https://www.acmicpc.net/problem/1120
1120번: 문자열
길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의
www.acmicpc.net
풀이
A와 B의 최대 길이는 50이기 때문에, A와 B의 최소 차이인 answer는 50으로 설정한다.
A와 B를 비교할 때 A의 시작 지점을 기준으로 탐색한다.
경우의 수는 (len(B) - len(A) + 1)이다.
문제의 예제를 예를 들면, (A: adaabcX, B: aababbc)와 (A: Xadaabc, B: aababbc)인 두 가지 경우의 수를 고려할 수 있다.(X 위치는 무조건 B와 일치함을 의미)
그리고나서 A의 문자 하나씩 비교하여 B문자와의 최소 차이 갯수(cnt)를 answer에 갱신한다.
코드
import sys
A, B = sys.stdin.readline().rstrip().split()
answer = 50
for i in range(len(B) - len(A) + 1):
cnt = 0
for j in range(len(A)):
if A[j] != B[i + j]:
cnt += 1
answer = min(answer, cnt)
print(answer)