문제 설명
소문자로만 이루어진 문자열 S가 있다고 가정해 봅시다. 우리는 원하는 만큼 여러 번의 이동(move)을 수행할 수 있습니다.
각 이동에서는 문자열의 앞쪽 K개 문자 중 하나를 선택해 제거한 뒤, 문자열의 맨 끝으로 옮깁니다. 목표는 임의의 횟수만큼 이동을 수행한 후 얻을 수 있는 사전순(lexicographically)으로 가장 작은 문자열을 찾는 것입니다.
예를 들어 입력이 "cabaa"이고 K = 3이라면, 출력은 "aaabc"가 됩니다.
해결 전략
이 문제는 다음과 같은 단계로 해결할 수 있습니다.
K > 1인 경우
문자열 S를 오름차순으로 정렬합니다.
정렬된 S를 그대로 반환합니다.
K가 2 이상이면 앞쪽 K개 문자 중 어떤 것이든 자유롭게 골라 끝으로 보낼 수 있기 때문에, 사실상 모든 문자를 원하는 순서대로 재배치할 수 있습니다. 따라서 정렬된 문자열이 항상 최적의 답이 됩니다.
K = 1인 경우
ret := S 로 초기화합니다.
n := S의 길이
i를 1부터 n 미만까지 1씩 증가시키며 반복합니다.
S의 첫 번째 문자를 잘라내어 맨 끝에 붙입니다(문자열 회전).
현재 S가 ret보다 사전순으로 작다면 ret = S로 갱신합니다.
K가 1일 때는 매번 첫 문자만 끝으로 옮길 수 있으므로, 발생 가능한 모든 회전(rotation) 형태를 비교하여 그중 가장 작은 값을 선택하면 됩니다.
최종적으로 ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 더 쉽게 이해할 수 있습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string orderlyQueue(string S, int K) {
if(K > 1){
sort(S.begin(), S.end());
return S;
}
string ret = S;
int n = S.size();
for(int i = 1; i < n; i++){
S = S.substr(1) + S.substr(0, 1);
if(S < ret) ret = S;
}
return ret;
}
};
main(){
Solution ob;
cout << (ob.orderlyQueue("cabaa", 3));
}입력
"cabaa", 3
출력
aaabc
복잡도 분석
K > 1인 경우에는 정렬에 O(n log n)의 시간이 소요됩니다. K = 1인 경우에는 n번의 회전마다 문자열 재구성과 비교가 이루어지므로 시간 복잡도는 O(n²)가 됩니다. 문자열의 길이가 짧은 경우에는 충분히 효율적으로 동작합니다.