문제 소개
문자열 s가 주어졌을 때, 문자열 안에서 두 문자의 위치를 최대 한 번만 교환(swap)하여 만들 수 있는 문자열 중 사전순으로 가장 작은(lexicographically smallest) 문자열을 찾는 것이 이번 문제의 목표입니다.
예를 들어 입력 문자열이 "zyzx"라면, 첫 번째 문자 z와 세 번째 문자 x를 맞바꿔 "xyzz"를 만들 수 있으며, 이것이 가능한 결과 중 가장 작은 값입니다.
알고리즘 접근 방법
이 문제는 그리디(greedy) 기법으로 효율적으로 해결할 수 있습니다. 핵심 아이디어는 각 위치 i에 대해 i 이후 구간에서 가장 작은 문자의 인덱스를 미리 계산해 두는 것입니다. 구체적인 단계는 다음과 같습니다.
temp:= 문자열 s와 같은 크기의 배열을 만들고 0으로 초기화합니다.m:= len(s) - 1 로 설정합니다.- i를 len(s)-1부터 0까지 거꾸로 순회하며 다음을 수행합니다.
- 만약 s[i] < s[m]이면, m := i 로 갱신합니다.
- temp[i] := m 을 저장합니다. 즉, temp[i]에는 "i부터 끝까지 구간에서 최솟값 문자의 위치"가 기록됩니다.
- i를 0부터 len(s)-1까지 순서대로 순회하며 다음을 수행합니다.
- a := temp[i]
- 만약 s[a] != s[i]라면(현재 위치보다 뒤쪽에 더 작은 문자가 존재한다면), 두 문자를 교환한 결과인 s[:i] + s[a] + s[i+1:a] + s[i] + s[a+1:] 를 반환합니다.
- 교환이 필요 없는 경우(이미 정렬된 문자열 등) 원본 문자열 s를 그대로 반환합니다.
예제 코드 (Python)
class Solution:
def solve(self, s):
temp = [0]*len(s)
m = len(s)-1
for i in range(len(s)-1, -1, -1):
if s[i]<s[m]: m=i
temp[i] = m
for i in range(len(s)):
a = temp[i]
if s[a] != s[i]:
return s[:i]+s[a]+s[i+1:a]+s[i]+s[a+1:]
return s
ob = Solution()
print(ob.solve("zyzx"))입력
zyzx
출력
xyzz
동작 원리 자세히 살펴보기
1. 오른쪽에서 왼쪽으로 스캔하는 이유
첫 번째 반복문은 문자열의 끝에서 시작점 방향으로 진행하면서, 각 인덱스 i에 대해 "i 이후(자기 자신 포함) 구간에서 가장 작은 문자의 위치"를 temp 배열에 저장합니다. 덕분에 두 번째 반복문에서 각 위치마다 교환 대상을 O(1) 시간에 바로 알 수 있습니다.
2. 동일한 최솟값이 여러 개일 때의 처리
스캔이 오른쪽에서 왼쪽으로 진행되고 갱신 조건이 엄격한 부등호(s[i] < s[m])이기 때문에, 최솟값 문자가 여러 번 나타나면 가장 오른쪽에 있는 위치가 선택됩니다. 이것이 유리한 이유는, 교환 시 밀려나는 큰 문자를 최대한 뒤쪽에 배치할 수 있어 결과 문자열이 더 작아지기 때문입니다. 예를 들어 "cbaa"에서 첫 문자 c와 교환할 'a'의 위치로 인덱스 3을 선택하면 "abac"가 되고, 인덱스 2를 선택하면 "abca"가 되는데, 전자가 더 작습니다.
3. 시간 및 공간 복잡도
문자열을 앞뒤로 각각 한 번씩 순회하므로 시간 복잡도는 O(n)이며, 보조 배열 temp를 사용하므로 공간 복잡도 역시 O(n)입니다.