Python으로 문자열을 t+t 형태(같은 문자열 두 개의 연결)로 만드는 최소 편집 횟수 계산하기

문제 설명

소문자로만 구성된 문자열 s가 주어져 있다고 가정해 보겠습니다. 우리는 문자열 안에서 임의의 문자를 삭제, 삽입, 또는 다른 문자로 교체하는 세 가지 연산을 자유롭게 사용할 수 있습니다. 목표는 어떤 문자열 t에 대해서든 s = t + t, 즉 동일한 문자열 두 개를 이어 붙인 형태가 되도록 만드는 데 필요한 최소 연산 횟수를 구하는 것입니다.

예를 들어 입력이 s = "pqrxqsr"이라면 정답은 2입니다. 'x'를 'p'로 바꾸고 's'를 삭제하면 문자열이 "pqrpqr"이 되는데, 이는 t = "pqr"일 때의 t + t와 정확히 일치하기 때문입니다.

접근 방법: 편집 거리(Edit Distance) 활용

이 문제는 편집 거리(Levenshtein Distance) 알고리즘을 응용하면 효율적으로 해결할 수 있습니다. 편집 거리란 한 문자열을 다른 문자열로 변환하기 위해 필요한 삽입·삭제·교체 연산의 최소 횟수를 의미합니다. 핵심 아이디어는 다음과 같습니다.

문자열 s를 모든 가능한 지점에서 앞부분과 뒷부분으로 나누어 봅니다.
각 분할 지점에서 앞부분(s[:i])과 뒷부분(s[i:]) 사이의 편집 거리를 계산합니다.
두 부분을 동일하게 만드는 데 드는 비용이 곧 편집 거리이므로, 모든 분할 지점 중 최솟값이 정답이 됩니다.

edit_distance() 함수 구현 단계

m := s1의 길이, n := s2의 길이로 설정합니다.
cur := 0부터 n까지의 값으로 초기화된 리스트를 생성합니다. (동적 계획법 테이블의 현재 행 역할)
i를 0부터 m-1까지 반복합니다.
- prev := cur (이전 행을 저장)
- cur := [i+1]과 n개의 0으로 구성된 새 리스트로 갱신
- j를 0부터 n-1까지 반복하며 다음을 수행합니다.
  - s1[i]와 s2[j]가 같으면: cur[j+1] := prev[j] (추가 연산 불필요)
  - 다르면: cur[j+1] := min(cur[j], prev[j], prev[j+1]) + 1 (삽입·삭제·교체 중 최소 비용 선택)
cur[n]을 반환합니다. 이것이 두 문자열 간의 편집 거리입니다.

메인 로직 단계

res := s의 길이로 초기화합니다. (모든 문자를 교체해야 하는 최악의 경우를 대비)
i를 0부터 len(s)-1까지 반복하며 res := min(edit_distance(s[:i], s[i:]), res)로 갱신합니다.
res를 반환합니다.

구현 예제

아래 구현을 통해 더 잘 이해해 보겠습니다.

def solve(s):
    def edit_distance(s1, s2):
        m, n = len(s1), len(s2)
        cur = list(range(n + 1))
        for i in range(m):
            prev, cur = cur, [i + 1] + [0] * n
            for j in range(n):
                cur[j + 1] = (prev[j]
                              if s1[i] == s2[j] else min(cur[j], prev[j], prev[j + 1]) + 1)
        return cur[n]

    res = len(s)
    for i in range(len(s)):
        res = min(edit_distance(s[:i], s[i:]), res)
    return res


s = "pqrxqsr"
print(solve(s))

입력

"pqrxqsr"

출력

복잡도 분석

편집 거리 한 번의 계산에 O(m × n)의 시간이 소요되며, 이를 문자열 길이만큼의 분할 지점마다 반복하므로 전체 시간 복잡도는 O(n³)입니다. 공간 복잡도는 DP 테이블에서 두 행(prev, cur)만 유지하므로 O(n)입니다.