-
[LeetCode] 899. Orderly Queue알고리즘 문제 풀이 2021. 9. 6. 17:14
문제 출처: https://leetcode.com/problems/orderly-queue/
Orderly Queue - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제
문자열 s와 정수 k가 주어진다. s의 첫 k문자 중 하나를 선택하고, 그 문자를 문자열의 맨 뒤로 보낼 수 있다.
몇 번의 이동을 통하여 사전적으로 가장 작은 문자열을 만들어 반환하라.
예제
Input: s = "cba", k = 1 Output: "acb" Explanation: In the first move, we move the 1st character 'c' to the end, obtaining the string "bac". In the second move, we move the 1st character 'b' to the end, obtaining the final result "acb".
Input: s = "baaca", k = 3 Output: "aaabc" Explanation: In the first move, we move the 1st character 'b' to the end, obtaining the string "aacab". In the second move, we move the 3rd character 'c' to the end, obtaining the final result "aaabc".
풀이
k=1일 때의 경우를 생각해보면, 문자열을 왼쪽 방향으로 회전을 시킨다고 생각할 수 있다. 이때 각각의 만들어지는 문자열을 비교하여 가장 작은 문자열을 찾아낼 수 있을 것이다.
문제는 k>1인 상황이다.
k>1상황 중에서도 가장 극한의 상황인 k=2일 때, 예제 s = "baaca"를 고려해보자.
사전 순에서 가장 작은 문자열을 찾는 것이 목표이기 때문에, 기본적으로 알파벳 순서로 s를 나열해야 한다. 그래서 우선 알파벳 "a"를 한 곳에 모으고자 한다.
origin s = baaca 1. select: b, moved_s = aacab 2. select: a, moved_s = acaba 3. select: a, moved_s = cabaa 4. select: a, moved_s = cbaaa
"a" 다음으로 작은 문자는 "b" 이기 때문에 "a" 뒤에 바로 "b" 문자가 와야 하며, "b" 다음에는 "c" 문자가 와야 가장 작은 문자가 될 것이다. 가능한가?
5. select: b, moved_s = caaab 6. select: c, moved_s = aaabc
"baaca" 와 같이 알파벳이 뒤섞여있는 문자열이 6번의 움직임으로 "aaabc"와 같이 정렬된 형태로 표현되었다.
한 가지 예이지만, k=2인 상황에서 문자열 s를 알파벳 순으로 정렬시킬 수 있음을 알 수 있다. 왜 정렬이 되는지에 대해 명확히 알고 싶다면, 버블 정렬의 상황을 이 문제에 응용하여 생각할 수 있다.
버블 정렬의 동작 과정을 생각해보면 고정되어 있는 배열 공간에 크기가 2인 윈도우가 슬라이딩 해가면서 윈도우가 가리키는 두 값을 큰 값은 오른쪽에 작은 값은 왼쪽에 위치시키는 것을 반복하면서 배열을 정렬해 간다.
이를 이 문제에 빗대면 윈도우가 고정되어 있는 채로 문자열이 조금씩 이동한다고 생각하면 된다. 결과적으로 핵심은 k=2, 즉, 윈도우의 크기가 2만 확보되면 정렬이 가능하다는 것이다.
가장 극한의 상황에서 정렬이 가능함을 알았기 때문에, 이보다 널널한 상황인 k>2에서는 당연히 주어진 문자열을 정렬시킬 수 있음을 확장하여 생각해볼 수 있다.
var orderlyQueue = function(s, k) { if (k == 1) { let minS = s; for (let i = 1; i < s.length; i++) { s = s.slice(1) + s.slice(0, 1); if (minS > s) { minS = s; } } return minS; } else { const chars = s.split(''); chars.sort(); return chars.join(''); } };
Github: https://github.com/opwe37/Algorithm-Study/blob/master/LeetCode/src/899.js
GitHub - opwe37/Algorithm-Study
Contribute to opwe37/Algorithm-Study development by creating an account on GitHub.
github.com
'알고리즘 문제 풀이' 카테고리의 다른 글
[LeetCode] 482. License Key Formatting (0) 2021.09.08 [LeetCode] 1629. Slowest Key (0) 2021.09.07 [LeetCode] 95. Unique Binary Search Trees II (0) 2021.09.03 [LeetCode] 565. Array Nesting (0) 2021.09.02 [LeetCode] 153. Find Minimum in Rotated Sorted Array (0) 2021.09.01