문제 개요
문자열 s가 주어졌을 때, 인접한 두 문자를 맞바꾸는 스왑(swap) 연산만을 사용해 이 문자열을 회문(palindrome)으로 만들어야 한다고 가정해 봅시다. 이때 필요한 스왑의 최소 횟수를 구하는 것이 목표입니다. 만약 어떤 방법을 사용해도 회문을 만들 수 없다면 -1을 반환합니다.
예를 들어 입력이 s = "xxyy"라면 출력은 2가 됩니다. 그 이유는 다음과 같습니다.
- 먼저 가운데의 "x"와 "y"를 스왑하여 문자열을 "xyxy"로 만듭니다.
- 그다음 앞의 두 문자 "x"와 "y"를 스왑하면 "yxxy"가 되고, 이 문자열은 회문입니다.
해결 접근 방법
이 문제를 해결하기 위해 다음 단계를 따릅니다.
1단계: 회문 생성 가능 여부 확인 (util 함수)
util()함수를 정의합니다. 이 함수는 문자열 s를 입력받습니다.seen이라는 새로운 딕셔너리(맵)를 생성합니다.- s의 각 문자 i에 대해 등장 횟수를 카운트합니다.
seen[i] = 기존 값 + 1 odd_count를 0으로 초기화합니다.- seen의 각 키-값 쌍을 순회하며, 등장 횟수가 홀수인 문자가 있으면
odd_count를 1씩 증가시킵니다. odd_count가 2가 되는 순간 False를 반환합니다. (홀수 길이 문자열은 홀수 개수 문자가 최대 1개만 허용되기 때문입니다.)- 모든 검사를 통과하면 True를 반환합니다.
2단계: 투 포인터(Two Pointer) 기법으로 최소 스왑 계산
swaps를 0으로 초기화합니다.util(s)가 참일 경우 다음을 수행합니다.left = 0,right = len(s) - 1로 설정합니다.- 문자열 s를 수정 가능한 문자 리스트로 변환합니다.
left < right인 동안 반복합니다.s[left]와s[right]가 다르면:k = right로 설정하고,k > left이면서s[k] != s[left]인 동안 k를 1씩 감소시켜 오른쪽부터 왼쪽 방향으로s[left]와 같은 문자를 찾습니다.k == left라면 매칭되는 문자를 찾지 못한 경우입니다. 이는 해당 문자가 전체에서 홀수 번 등장하는 문자이므로, 한 칸 옆의 문자와 스왑하고swaps를 1 증가시킵니다.- 그렇지 않다면(오른쪽 구간에서 매칭 문자를 찾은 경우), 찾은 위치 k부터 right까지 문자를 한 칸씩 오른쪽으로 밀어내며 스왑할 때마다
swaps를 1씩 증가시킵니다. - 양쪽 처리가 끝나면
left는 1 증가,right는 1 감소시킵니다.
s[left]와s[right]가 같다면 별도의 스왑 없이left를 1 증가,right를 1 감소시킵니다.
- 반복이 끝나면 누적된
swaps값을 반환합니다.
util(s)가 거짓이라면 회문을 만들 수 없으므로 -1을 반환합니다.
파이썬(Python) 구현 예제
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
class Solution:
def solve(self, s):
def util(s):
seen = {}
for i in s:
seen[i] = seen.get(i, 0) + 1
odd_count = 0
for k, val in seen.items():
if val & 1 == 1:
odd_count += 1
if odd_count == 2:
return False
return True
swaps = 0
if util(s):
left = 0
right = len(s) - 1
s = list(s)
while left < right:
if s[left] != s[right]:
k = right
while k > left and s[k] != s[left]:
k -= 1
if k == left:
swaps += 1
s[left], s[left + 1] = s[left + 1], s[left]
else:
while k < right:
s[k], s[k + 1] = s[k + 1], s[k]
k += 1
swaps += 1
left += 1
right -= 1
else:
left += 1
right -= 1
return swaps
return -1
ob = Solution()
s = "xxyy"
print(ob.solve(s))입력
"xxyy"
출력
2
정리
이 알고리즘은 먼저 각 문자의 등장 횟수를 세어 회문 생성 가능 여부를 판별한 뒤, 양쪽 끝에서부터 투 포인터를 이동시키며 일치하지 않는 문자를 가장 가까운 매칭 위치까지 스왑하는 방식으로 동작합니다. 시간 복잡도는 O(n²)이며, 공간 복잡도는 O(n)입니다. 문자열이 길지 않은 경우 효율적으로 활용할 수 있는 직관적인 해법입니다.