백준 1120번 문자열 Python

백준 1120번 문자열 Python 풀이

문제

길이가 다른 두 문자열 A, B가 주어집니다.

A의 앞이나 뒤에 문자를 붙여서 B와 길이가 같아질 때,

두 문자열의 서로 다른 문자 개수(= 차이)를 최소로 만드는 문제입니다.

즉, A를 B의 일부에 “겹쳐서” 비교했을 때,

가장 비슷한 구간을 찾는 것이 목표입니다.

테스트케이스

입력	출력	설명
adaabc aababbc	2	B의 여러 위치에 A를 겹쳐 비교했을 때 최소 차이 2
hello xello	1	첫 글자만 다름
koder topcoder	1	top(koder) 구간에서 차이 1
abc topabcoder	0	abc 부분이 완전히 일치
giorgi igroig	6	모든 문자가 다름

문제풀이 아이디어

1. 핵심 아이디어

• 문자열 A를 B 위에 하나씩 이동시켜가며 비교합니다.
• 즉, B의 i번째부터 i+len(A)까지 부분 문자열을 잘라서 A와 비교합니다.
• 각 비교마다 서로 다른 문자 개수를 센 후, 그 중 최솟값을 출력합니다.

2. 이유

• A의 길이가 B보다 작거나 같으므로,
• 가능한 겹침 시작 위치는 0부터 len(B)-len(A)까지입니다.
• 모든 경우를 전부 비교해도 최대 50×50 = 2500번이므로 충분히 빠릅니다.
• 따라서 완전탐색(브루트포스)으로도 해결이 가능합니다.

3. 절차

• 문자열 A, B 입력 받기
• 가능한 모든 시작 위치(i)에 대해
  • B[i : i+len(A)] 구간 추출
  • A와 비교하여 다른 글자 수 세기
• 최소 차이 갱신 후 출력

전체코드

def diff_str(X: str, Y: str):
    n1 = len(X)
    cnt = 0
    for x, y in zip(X, Y):
        if x != y:
            cnt += 1
    return cnt


X, Y = input().split()
N1 = len(X)
N2 = len(Y)
min_cnt = 1000  # 충분히 큰 수로 초기화

for i in range(N2 - N1 + 1):
    diff = diff_str(X, Y[i:N1 + i])
    if diff < min_cnt:
        min_cnt = diff

print(min_cnt)

결론

이 문제는 브루트포스로 모든 겹침 위치를 검사해도 충분히 해결 가능합니다.

시간 복잡도는 약 O(N × M) (N ≤ 50, M ≤ 50)으로 매우 작습니다.

즉,

• “A를 B 안에서 한 칸씩 밀어가며 겹쳐 비교한다.”
• 각 비교에서 “서로 다른 글자 수를 세고 최소값을 출력한다.”

이 간단한 방법으로 정답을 정확히 구할 수 있습니다.