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의 차이를 최소가 되도록 했을 때, 그 차이를 출력하시오.

예제 입력 1 

adaabc aababbc

예제 출력 1 

2

예제 입력 2 

hello xello

예제 출력 2 

1

예제 입력 3 

koder topcoder

예제 출력 3 

1

예제 입력 4 

abc topabcoder

예제 출력 4 

0

예제 입력 5 

giorgi igroig

예제 출력 5 

6

해석: 처음에 알파벳 추가까지 고려해야하는 줄 알고 코드 구현을 고민하는 과정이 어려웠다. 비교해야하는 문자열 A를 B에 하나하나 비교해서 알파벳을 추가하는 경우를 생각했다. 그러나 A 문자열을 한 칸씩 이동하면서 비교했을 때 문자열 B에 최대로 일치하는 구간을 찾은 다음에 빈자리에 알파벳을 B와 똑같이 추가하면 되는거니까, 굳이 알파벳 추가까지 구현하지 않아도 된다. 그러므로 A의 크기만큼 한칸씩 이동하면서 B와 A가 최대로 일치하는 구간을 찾은 뒤, 남은 자리에는 B와 똑같은 알파벳으로 추가된다고 가정하고 A와 B의 최소를 구하면 된다. 직접 몇개의 예시를 그려봤을 때 이해하기도 쉽고 그 패턴을 찾을 수 있었다. 
첫번째 예시처럼 A가 adaabc고, B가 aababbc면

1) 

aababbc

adaabc

oxxooxo

2) 한칸 이동!

aababbc

 adaabc

ooxoxoo

👉 위와 같이 a가 B보다 길이가 1만큼 작아서 B에서의 비교할 자리는 총 2군데가 되고, 빈 자리에는 b와 같은 알파벳이 온다고 가정했을 때, a가 위치한 자리 중에 b와 알파벳이 다른 자리만 세주면 된다. o가 일치, x가 불일치  
세번째 예시처럼 a가 koder고, b가 topcoder면
1)

topcoder
koder

xxxxxooo

2)

topcoder

 koder

oxxxxxoo

3)

topcoder

  koder

ooxxxxxoo

4)

topcoder

    koder

oooxoooo

👉 a가 B보다 길이가 3만큼 작아서, B에서의 비교할 자리는 4군데가 되고, 첫번째 예시처럼 똑같이 경우의 수를 구한 뒤, 그 중 차이의 개수가 제일 최소가 되는 값을 반환한다. 

import sys
a, b = input().split()

result = list()

# 두 문자열 길이의 차이만큼 반복
for i in range(len(b) - len(a) + 1):
    cnt = 0 # 다른 문자열 개수 세는 변수 초기화

    # 반복문을 통해 b의 인덱스를 +i 해주면서 a의 문자열과 비교
    for j in range(len(a)):
        # 다른 문자열이면 + 1 세기
        if a[j] != b[j + i]:
            cnt += 1

    # b의 인덱스를 +i 해주면서 비교했을 때 a의 문자열과 다른 문자열 개수를 리스트에 추가
    result.append(cnt)

# 다른 문자열의 개수 차이가 최소인 경우 출력
print(min(result))

✨ 따라서 바깥쪽 반복문에서 0부터 a와 b의 길이 차이만큼 돌고,  안쪽 for문에서 a의 크기만큼 a를 b와 대조한다.
a의 인덱스 값이 j일 때 b의 인덱스 값은 j+i값이 된다.