문제 소개
두 문자열 S와 T가 주어졌다고 가정해 보겠습니다. 두 문자열은 서로 같은 문자들을 다른 순서로 배열한 관계, 즉 순열(permutation)입니다. 허용된 연산은 단 하나입니다. S의 맨 앞 또는 맨 뒤 문자를 제거한 뒤, 문자열의 임의의 위치에 다시 삽입하는 것입니다. 이 연산만으로 S를 T로 변환할 때 필요한 최소 연산 횟수를 구하는 것이 이 문제의 목표입니다.
예를 들어 입력이 s = "zyvxw", t = "vwxyz"라면 출력은 3입니다. 실제 변환 과정은 다음과 같습니다.
'w'를 제거하고 'v' 뒤에 삽입 → "zyvwx"
'z'를 제거하고 'x' 뒤에 삽입 → "yvwxz"
'y'를 제거하고 'x' 뒤에 삽입 → "vwxyz"
접근 방법
핵심 아이디어는 의외로 간단합니다. S 안에서 T에 순서 그대로(부분 수열 형태로) 등장하는 가장 긴 연속 구간을 찾는 것입니다. 이 구간은 손댈 필요가 없고, 구간 밖의 나머지 문자들은 각각 한 번씩 제거 후 삽입하면 되므로 정답은 n - (최대 구간 길이)가 됩니다.
알고리즘의 진행 과정은 다음과 같습니다.
ans와 n을 문자열 s의 길이로 초기화합니다.
i를 0부터 n-1까지 반복합니다.
k를 0으로 초기화합니다.
j를 i부터 n-1까지 반복하며, 인덱스 k부터 탐색을 시작해 s[j]와 일치하는 문자를 t에서 찾습니다.
일치하는 문자를 발견하면 ans를 min(ans, n - (j - i + 1)) 값으로 갱신한 뒤 내부 루프를 빠져나옵니다.
바깥 반복이 진행될 때마다 k를 1씩 증가시켜 탐색 시작 위치를 뒤로 밀어냅니다.
모든 반복이 끝나면 ans를 반환합니다.
세 겹의 반복문을 사용하므로 시간 복잡도는 O(n³)이지만, 로직이 직관적이라 이해하기 쉬운 접근 방식입니다.
구현 예제
아래 파이썬 코드로 더 자세히 살펴보겠습니다.
class Solution:
def solve(self, s, t):
ans = n = len(s)
for i in range(n):
k = 0
for j in range(i, n):
for k in range(k, len(t)):
if s[j] == t[k]:
ans = min(ans, n - (j - i + 1))
break
k += 1
return ans
ob = Solution()
s = "zyvxw"
t = "vwxyz"
print(ob.solve(s, t))
입력
"zyvxw", "vwxyz"
출력
3
위 예제에서 s = "zyvxw"와 t = "vwxyz" 사이에 순서가 유지된 채 공통으로 등장하는 가장 긴 구간은 "vx"(길이 2)입니다. 따라서 나머지 3개의 문자('z', 'y', 'w')만 각각 한 번씩 옮기면 되고, 결과적으로 최소 연산 횟수는 3이 됩니다.