👩‍💻🔠 [baekjoon] 1120번: 문자열

🖍️ solution

import sys

"""
[시간]
1) 22:10 ~ 22:32

[요약]
1) 두 문자열 X와 Y의 차이: X[i] ≠ Y[i]인 i의 개수
    - X=”jimin”, Y=”minji”이면, 둘의 차이는 4
2) A ≤ B, 두 문자열의 길이가 똑같아 지도록 아래 연산 선택
    - A의 앞에 아무 알파벳이나 추가한다.
    - A의 뒤에 아무 알파벳이나 추가한다.
=> A와 B의 길이가 같으면서, A와 B의 차이를 최소로 하는 프로그램
"""

a, b = map(str, sys.stdin.readline().split())
slicer, checker = len(a), len(b) - len(a) + 1

tmp_min = 99999
for i in range(checker):
    count = 0
    tmp_b = b[i:i+slicer]
    for j in range(slicer):
        if a[j] != tmp_b[j]:
            count += 1
    tmp_min = min(tmp_min, count)
print(tmp_min)

💡 idea

• 1) 두 문자열의 길이 차이 구하기
  • 문자열 A를 B의 subsequence 로 간주하고, 가장 왼쪽 자리부터 차례로 대입
  • A와 B의 차이를 계산하고 임시로 값을 저장, 그 중에서 최소값을 결과로 출력

문제는 두 문자열의 차이가 최소가 되도록 문자열 A를 적절히 조작하는 것이었다. 다만 차이가 최소가 되는 방향으로 조작하려면 무조건 빈 자리수에 B의 글자를 그대로 대입하면 된다. 따라서 A의 빈자리에 어떤 글자를 넣을지 그런 경우의 수는 고려할 필요가 없다.

A를 B의 하위 문자열이라고 생각하고 B의 가장 왼쪽부터 A의 길이만큼의 문자열과 A를 대조해 차이를 구하고, 그다음 B의 가장 왼쪽+1부터 A의 길이만큼의 문자열과 다시 차이를 구하고, 이 과정을 계속 반복해 가장 최소가 되는 경우의 값을 출력하면 정답이 된다.