[LeetCode] 899. Orderly Queue

문제 : https://leetcode.com/problems/orderly-queue/

---

문자열 s, 정수 k가 주어진다. 문자열 s의 앞에서부터 k개의 문자들 중 하나를 s문자열의 가장 뒤로 이동시킬 수 있다.

이동횟수와 상관없이 s 문자열의 문자를 이동시켰을 때 얻을 수 있는 문자열들 중 사전순으로 가장 빠른 문자열을 구하라.

---

K가 2이상인 경우, s문자열의 문자들로 만들 수 있는 사전순으로 가장 빠른 문자열이 정답이 될 수 있다. (정렬된 문자열이 정답)

왜냐하면 K가 2이상의 경우 문자들의 개수가 달라지지 않는 한에서 어떤 문자열들도 만들 수 있기 때문이다.

증명해보자.

한 번에 많은 것을 하지 않고 하나의 문자만 올바른 위치로 옮긴다고 생각하면 쉽다.

옮겨야 될 문자를 가장앞에 keep해뒀다가 가장 뒤에 있는 문자가 옮겨야 될 문자의 바로 앞 문자면 keep해둔 문자를 가장 뒤로 옮긴다. 적절할 때가 오지 않으면 계속 로테이션 하면 된다. (옮기려는 문자를 제외한 문자들의 정렬은 유지되어야 한다.)

작은 수 부터 뒤로 옮긴다.

 

예를 들어,

E D A C B 라는 문자열이 있다고 치자.

그리고 K가 3이라고 한다면 정렬하는 방법은 다음과 같다.

1. [E D A] C B -> E D C B A (처음에는 사전순으로 가장 앞서는 수를 가장 뒤로 보내준다.)

2. [E D C] B A -> [D C B] A E -> [C B A] E D -> [B A E] D C -> [B E D] C A -> E D C A B

3. [E D C] A B -> [D C A] B E -> [C A B] E D -> [C B E] D A -> [C E D] A B -> E D A B C

4. [E D A] B C -> [D A B] C E -> [D B C] E A -> [D C E] A B -> [D E A] B C -> E A B C D

5. [E A B] C D -> A B C D E

 

K가 1인 경우는 Keep 해둘 공간이 없으므로 로테이션하는 모든 경우를 모두 탐색해서 정답을 구한다.

E D C B A, D C B A E, C B A E D, B A E D C, A E D C B

 

시간복잡도는 N = |S| 라한다면,

K가 1인 경우 O(N), K가 2이상인 경우 O(NlogN).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/899.%20Orderly%20Queue.cpp