[백준] 1120 파이썬(python) : 문자열 - 문자속비교(★)

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

1120번: 문자열

 

 

처음 문제를 접했을때 앞뒤에 넣어줄 소문자 알파벳을 모두 다 배열에다 넣은채로 만들어서 하나하나 길이차이 만큼 비교해줘야하나 생각했는데 아니었다. 문자열 b보다 짧은 문자열a를 비교할때 a의 앞뒤에는 어떤 알파벳이 들어가는지 신경쓰지 않아도 된다.

어차피 차이의 개수만 출력하면 되므로 앞뒤에 들어갈 문자는 알아서 가장 비슷한게 들어가겠구나 생각하면 된다. 즉, 차이의 최소값을 구하라고 했으므로 바꿀 수 없는 부분에만 집중하면 된다.

 

import sys
a, b = sys.stdin.readline().rstrip().split()
ans = []
for i in range(len(b)-len(a)+1): #1
    cnt = 0
    for j in range(len(a)): #2
        if a[j] != b[i+j]: #3
            cnt += 1
    ans.append(cnt)
print(min(ans))

 

#1 : b가 a보다 길거나 같다고 했으니까 b의 길이에서 a의 길이를 뺀 만큼 반복

#2 : 길이가 짧은 a가 길이가 긴 b의 안에 들어가서 비교해줘야 하므로 a의 길이만큼 반복

#3 : b의 인덱스는 한칸씩 올라가게 설정

 

예제1을 예시로 들면

adaabc

 

(aababb)c => 3

a(ababbc) => 2

 

이 둘중에서 가장 작은 값은 2이고 정답을 출력하면 된다.

3이 나오는 경우에선 a에 맨뒤에 알파벳 c를 넣으면 b와 차이가 최소가 될것이고, 2가 나오는 경우에선 a의 맨 앞에 알파벳 벳 a를 넣으면 b와의 차이가 2가 된다. 즉, 앞뒤에 어떤 알파벳을 넣는지는 중요하지 않다.

 

 

한 문자열 속에 다른 문자열을 넣어서 비교하는 문제였다. 여기서는 차이를 구하라고 했지만 다른 문제에선 다르게 물어볼 수도 있으므로 비교하는 방법인 #1, #2, #3은 외우고 있어야겠다.