[BOJ]1120. 문자열

문제:

길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] != Y[i]인 i의 개수이다. 예를 들어, X="jimin", Y="minji"이면, 둘의 차이는 4이다.

두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다.

 

 1. A의 앞에 아무 알파벳이나 추가한다.

 2. A의 뒤에 아무 알파벳이나 추가한다.

 

이때, A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램을 작성하시오.

 

입력:

첫째 줄에 A와 B가 주어진다. A와 B의 길이는 최대 50이고, A의 길이는 B의 길이보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

 

출력:

A와 B의 길이가 같으면서, A와 B의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

풀이방법:

문자열을 비교하는 단순한 알고리즘을 사용하면 된다. 알파벳을 추가할 때 앞인지 뒤인지가 중요한 것이 아니라 추가하는 행위자체가 중요한 것이다. 따라서 즉 A와 B가 얼마나 다른지가 중요한 것이다. A를 한칸씩 밀어가면서 일치하지 않을 때마다 count를 하나씩 늘리고 이 것이 최소가 되는 count을 저장해주면 된다.

n,m=input().split()
answer=51
if len(n)==len(m):
    count=0
    for i in range(len(m)):
        if n[i]!=m[i]:
            count+=1
    print(count)
else:
    for i in range(len(m)-len(n)+1):
        count=0
        for j in range(len(n)):
            if n[j] != m[j+i]:
                count+=1
        answer=min(answer,count)
    print(answer)

문제링크:

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