[Brute Force] 백준 1120 문자열 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1120번: 문자열

 

 

 

2. 문제 풀이

 두 문자열이 입력으로 주어집니다. 이후 긴 문자열의 길이와 같아질 때까지 짧은 문자열의 앞뒤로 아무 알파벳이나 추가합니다. 길이가 같아졌을 때, 두 문자열의 차이가 최소가 되도록 만들어야 합니다.

 

2022.01.16 - [Algorithm] - [Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

[Algorithm] 브루트 포스(Brute Force)는 노가다 기법?

 문제에서 설명한 방식대로 구하려면 너무 복잡합니다. 반대로 긴 문자열의 앞뒤를 짤라서 짧은 문자열을 만드는 게 쉽습니다. 그리고 그것보다 더 쉬운 건, 슬라이딩 윈도우처럼 긴 문자열 내를 짧은 문자열과 비교하면서 탐색하는 것입니다. 

 

 

 

3. 코드

import sys
input = sys.stdin.readline

# 입력
A, B = input().rstrip().split()

# 브루트포스
if len(A) > len(B):  # 짧은 길이가 A
    A, B = B, A

# 두 문자열 차이 계산
def diff(a, b):
    n = len(a)
    res = 0
    for i in range(n):
        if a[i] != b[i]:
            res += 1
    return res

# A 길이만큼 B를 순회하며 판별
min_diff = 50
for i in range(len(B)-len(A)+1):
    min_diff = min(min_diff, diff(A, B[i:i+len(A)]))
print(min_diff)

  두 문자열의 차이를 diff 함수가 계산하고, 긴 문자열 내를 한 칸씩 이동하며 짧은 문자열과 비교합니다.

 

긴 문자열: topcoder
짧은 문자열: koder

1회) 4
topcoder
koder


2회) 5
topcoder
 koder

3회) 5
topcoder
   koder

4회) 1
topcoder
    koder

 예제 입력 4를 예시로 들면, 위와 같은 과정을 거쳐 A, B의 최소 차이를 찾아냅니다.