[백준🥈4] #1120 문자열 (python)

1120번: 문자열 (acmicpc.net)

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

 

✔️ Code

A, B = input().split()
min_value = 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
    min_value = min(min_value, cnt)

print(min_value)

 

✏️ Comment

A 문자열의 앞과 뒤에 문자가 추가될 수 있는 경우를 다 따져서 최솟값을 구하자니 너무 복잡해질 것 같아서 풀이를 고민했다.
그런데 도저히 좋은 풀이법이 생각나지 않아서 결국 구글링 해봤다.. 답은 생각보다 간단했다.

어차피 A와 B를 비교했을 때 같은 문자의 갯수가 최대한 많아지게, 즉, 다른 문자의 갯수가 최소한이 되도록 하는 것이 목표이기 때문에
A의 앞이나 뒤에 추가할 문자 혹은 문자열은 B와 같은 걸 넣는다고 가정하고 문제를 풀면 된다.

A와 B 가정
A : abc
B : cdabc

1번째 비교
A : abc
B : (cda)bc

2번째 비교
A : abc
B : c(dab)c

3번째 비교
A : abc
B : cd(abc)c

4번째 비교
A : abc
B: cda(bcc)

코드의 이중 for문을 풀어써보자면 이렇게 비교가 되는 것이다. 
위의 예시를 보면 3번째 경우가 min_value의 값이 가장 최소가 되는 경우라는 것을 확인할 수 있다.
이때, A와 B 둘 다 abc라는 같은 문자열을 가지므로 A 앞에 cd, 뒤에 c를 추가해준다고 가정하면 min_value의 값은 0이 된다.