BOJ 1120 - 문자열

풀이

---

두 문자열의 차이를 최소화하는 문제이다.

예제를 살펴보자.

문자열 a : adaabc

문자열 b : aababbc

문자열 b 는 문자열 a 보다 항상 길거나 같기 때문에 c 라는 변수에 두 문자열 길이의 차를 저장해준다.

위 예제의 경우 c 는 1 이다.

두 문자열을 비교하기 위해선 문자열 a 가 문자열 b 의 길이와 같아져야한다.

이때 문자열 a 의 앞이나 뒤에 아무 알파벳을 추가하게되는데 두 문자열의 차이를 최소화하기 위해선 문자열 a 에 추가된 알파벳이 문자열 b 의 알파벳들과 같아야한다.

위 예제를 다시 살펴보자.

문자열 a 는

1. aadaabc

2. adaabcc

둘 중 하나가 될 것이고

이 두 문자열을 문자열 b 와 비교한 뒤 둘 중 최소한의 차이를 구해주면된다.

문제풀이를 작성하면서 든 생각이지만 애초에 b[i:len(a)+i] 로 문자열 b 를 문자열 a 에 맞춰 슬라이싱 하면서 비교하는 방법이 더 깔끔했을 것 같다.

소스코드

---

import sys
 
input = sys.stdin.readline
 
a, b = input().split()
 
 
def compare(a, b):
    c = 0
    for i in range(len(b)):
        if a[i] != b[i]:
            c += 1
    return c
 
 
c = len(b) - len(a)
min_c = 51
 
for i in range(c + 1):
    d = b[:(c - i)] + a + b[-i:]
    min_c = min(min_c, compare(d, b))
 
print(min_c)

References

---

• BOJ 1120 - 문자열