1120번 - 문자열

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

1120번: 문자열

문제를 처음 보고 든 생각은 문자열 A를 덱으로 만들어서 완전 탐색으로 앞에서도 넣어보고 뒤에서도 넣어보며 최솟값을 찾으려고 했다.

하지만 구현하면서 이거보다 더 좋은 방법이 있을 것 같다는 생각이 들어서 힌트를 살짝 보았다.

 

# 문자열
import sys
input = sys.stdin.readline

A, B = input().split()
answer = 50

def cal_diff(a, b): # 두 문자열의 차이 구하는 함수
    global answer
    dif = 0
    for i in range(len(a)):
        if a[i] != b[i]:
            dif += 1
    answer = min(answer, dif)
    return answer


if len(A) == len(B):
    cal_diff(A, B)
else:
    for i in range(len(B)-len(A)+1):
        cal_diff(A, B[i:i+len(A)])

print(answer)

A와 B를 입력받은 후, A와 B의 길이가 같을 때는 바로 두 문자열의 차이를 구하는 함수인 cal_diff 함수를 호출하여 answer를 갱신한다.

하지만, 길이가 다를 때는 A에 원소를 추가해야 한다.

이때 생각을 바꾸어 A에 값을 직접 추가하는 것 대신에 B를 A의 길이만큼만 인덱싱하여 cal_diff 함수를 호출한다. 

 

즉, B의 인덱싱 범위에 포함되지 않은 원소는 A에 그 원소들을 추가하였다고 생각하는 것이다.

예를 들어, A: "abc" B: "abcde" 라면 B를 A의 길이에 맞춰 자른 뒤 cal_diff 함수를 호출하는 것이다. 

그렇게 되면 "abc", "bcd", "cde" 이렇게 cal_diff 함수가 세 번 호출될 것이다.

첫 번째 경우에는 A는 뒤에 원소를 추가하여 "abcde" 라는 문자열이 될 것이고 B와 일치하기 때문에 answer는 0으로 갱신된다.

두 번째 경우의 A는 앞과 뒤에 원소를 추가하여 "aabce"가 될 것이다. 이 경우에는 차이가 3이 되므로 answer가 갱신되지 않는다. 

세 번째 경우도 동일한 방법으로 생각하면 된다.