Python에서 문자열 s가 t의 부분 문자열이 되도록 만드는 최소 연산 횟수 구하기

두 개의 문자열 s와 t가 주어졌을 때, t가 s의 부분 문자열이 되도록 만들기 위해 필요한 최소 연산 횟수를 구하는 문제를 살펴보겠습니다. 여기서 각 연산은 s의 임의의 위치를 하나 선택하여 해당 위치의 문자를 다른 문자로 변경하는 것을 의미합니다.

예를 들어, 입력이 s = "abbpqr", t = "bbxy"라고 가정해 보겠습니다. 이때 출력은 2가 됩니다. 부분 문자열 "bbpq"를 선택한 뒤 'p'를 'x'로, 'q'를 'y'로 바꿔주면 되기 때문입니다.

문제 해결 접근 방법

이 문제는 슬라이딩 윈도우(Sliding Window) 기법으로 효율적으로 해결할 수 있습니다. 해결 단계는 다음과 같습니다.

• k := t의 길이, n := s의 길이로 설정합니다.
• ans := 10^10 (비교를 위한 매우 큰 값으로 초기화)
• i를 0부터 n - k까지 반복합니다.
  • ss := s의 인덱스 i부터 i+k-1까지의 부분 문자열
  • ans := ans와 (ss와 t 사이에서 일치하지 않는 문자 개수) 중 더 작은 값으로 갱신
• 반복이 끝나면 ans를 반환합니다.

t의 길이와 같은 모든 후보 구간을 s 위에서 한 칸씩 이동하며 검사하고, 그중 문자 교체가 가장 적게 필요한 구간의 교체 횟수가 곧 정답이 됩니다. 시간 복잡도는 O(n × k)입니다.

예제 코드

class Solution:
    def solve(self, s, t):
        k, n = len(t), len(s)
        ans = 10**10
        for i in range(n - k + 1):
            ss = s[i:i+k]
            ans = min(ans, sum(ss[j]!=t[j] for j in range(k)))
        return ans
ob = Solution()
print(ob.solve("abbpqr", "bbxy"))

입력

"abbpqr", "bbxy"

출력

2

코드에서 sum(ss[j]!=t[j] for j in range(k)) 부분은 현재 윈도우 내에서 t와 다른 문자의 개수를 계산합니다. 불리언 값은 Python에서 True가 1, False가 0으로 처리되므로 이처럼 간결하게 일치하지 않는 문자 수를 합산할 수 있습니다.