두 문자열 S와 T가 서로 아나그램(anagram, 동일한 문자들을 재배치한 관계)이라고 가정해 보겠습니다. 이때 구해야 할 것은 문자열 S를 T와 완전히 같게 만들기 위해 필요한 최소 스왑(문자 교환) 횟수입니다.
예를 들어 입력이 S = "kolkata", T = "katloka"라면 결과는 3이 됩니다. [katloka(주어진 값), kotlaka, koltaka, kolkata]의 순서로 문자를 교환하면 목표를 달성할 수 있기 때문입니다.
해결 접근 방법
이 문제는 재귀 호출과 백트래킹(backtracking)을 활용해 해결할 수 있습니다. 각 위치에서 필요한 문자를 뒤쪽에서 찾아 교환한 뒤, 다음 위치에 대해 같은 과정을 반복하며 가능한 모든 경우 중 최솟값을 선택하는 방식입니다.
구체적인 알고리즘 단계는 다음과 같습니다.
util()함수를 정의합니다. 이 함수는 S, T, 인덱스 i를 매개변수로 받습니다.- i가 S의 길이보다 크거나 같으면 0을 반환합니다.
- S[i]와 T[i]가 같다면 교환이 필요 없으므로 util(S, T, i + 1)을 그대로 반환합니다.
- x := T[i]로 목표 문자를 저장합니다.
- ret := 99999로 초기화합니다(사실상 무한대 역할).
- j를 i+1부터 T의 길이까지 반복하며 다음을 수행합니다.
- x가 S[j]와 같다면 S[i]와 S[j]를 교환(swap)합니다.
- ret을 ret과 (1 + util(S, T, i + 1)) 중 작은 값으로 갱신합니다.
- S[i]와 S[j]를 다시 원래대로 되돌려 다른 경우도 탐색할 수 있게 합니다(백트래킹).
- ret을 반환합니다.
- 메인 메서드에서는 util(S, T, 0)을 호출해 최종 결과를 얻습니다.
파이썬 구현 예제
class Solution:
def util(self, S, T, i):
S = list(S)
T = list(T)
if i >= len(S):
return 0
if S[i] == T[i]:
return self.util(S, T, i + 1)
x = T[i]
ret = 99999
for j in range(i + 1, len(T)):
if x == S[j]:
S[i], S[j] = S[j], S[i]
ret = min(ret, 1 + self.util(S, T, i + 1))
S[i], S[j] = S[j], S[i]
return ret
def solve(self, S, T):
return self.util(S, T, 0)
ob = Solution()
S = "kolkata"
T = "katloka"
print(ob.solve(S, T))
입력
"kolkata", "katloka"
출력
3
동작 원리 요약
이 알고리즘은 현재 위치 i의 문자가 T[i]와 일치하지 않을 때, 뒤쪽에 있는 동일한 문자를 앞으로 가져오는 방식으로 진행됩니다. 교환을 수행한 후 나머지 부분에 대해 재귀적으로 최소 스왑 수를 계산하고, 가능한 모든 후보 교환을 시도해 본 뒤 그중 가장 작은 값을 선택합니다. 이러한 백트래킹 기법 덕분에 전체 문자열을 T로 변환하는 데 필요한 최소 교환 횟수를 정확히 구할 수 있습니다.