[리트코드][JAVA] 899. orderly-queue (정렬된 큐)

💡 문제
orderly-queue (https://leetcode.com/problems/orderly-queue/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

 

📝 선행 개념

• 시간 복잡도:
  • k == 1: O(n^2)
  • k >= 2: O(n log n)
• 공간 복잡도:
  • k == 1: O(n)
  • k >= 2: O(n)

---

🤓 문제 풀이

문제 번역

문자열 s와 정수 k가 주어집니다. s의 처음 k개의 문자 중 하나를 선택하여 문자열 끝에 추가할 수 있습니다. 주어진 단계를 여러 번 적용한 후 얻을 수 있는 사전 순으로 가장 작은 문자열을 반환하세요.

---

 

예시 1:

• 입력: s = "cba", k = 1
• 출력: "acb"
• 설명:
  • 첫 번째 , 첫 번째 문자 'c'를 끝으로 이동하여 문자열 "bac"를 얻습니다.
  • 두 번째 단계에서, 첫 번째 문자 'b'를 끝으로 이동하여 최종 결과 "acb"를 얻습니다.

예시 2:

• 입력: s = "baaca", k = 3
• 출력: "aaabc"
• 설명:
  • 첫 번째 단계에서, 첫 번째 문자 'b'를 끝으로 이동하여 문자열 "aacab"를 얻습니다.
  • 두 번째 단계에서, 세 번째 문자 'c'를 끝으로 이동하여 최종 결과 "aaabc"를 얻습니다.

제약 조건:

• 1 <= k <= s.length <= 1000
• s는 영문 소문자로 구성됩니다.

---

문제풀이

이 문제를 풀기 위해서는 두 가지 경우를 생각했다.

경우 1: k == 1

이 경우에는 s의 처음 문자 하나만을 뒤로 보낼 수 있으므로, 문자열을 회전하여 가능한 모든 경우를 고려해야 합니다. 그런 다음, 가장 작은 사전 순 문자열을 찾는다.

예를 들어, **s = "cba"인 경우:

• "cba" -> "bac" -> "acb"
• 이 중 사전 순으로 가장 작은 문자열은 "acb"입니다.

경우 2: k >= 2

이 경우에는 s의 처음 두 문자 이상을 뒤로 보낼 수 있으므로, 어떤 두 문자도 서로 교환할 수 있습니다. 이는 모든 문자를 정렬할 수 있다는 것을 의미합니다.

예를 들어, **s = "baaca"인 경우:

• "baaca"를 사전 순으로 정렬하면 "aaabc"가 됩니다.

---

import java.util.Arrays;

class Solution {
    public String orderlyQueue(String s, int k) {
        // k가 1인 경우
        if (k == 1) {
            String smallest = s; // 사전 순으로 가장 작은 문자열을 저장할 변수
            // 문자열의 각 위치에서 시작하여 모든 회전된 문자열을 확인
            for (int i = 0; i < s.length(); i++) {
                // 현재 회전된 문자열을 생성
                String rotated = s.substring(i) + s.substring(0, i);
                // 현재 회전된 문자열이 지금까지의 가장 작은 문자열보다 작으면 업데이트
                if (rotated.compareTo(smallest) < 0) {
                    smallest = rotated;
                }
            }
            return smallest; // 가장 작은 문자열 반환
        } else {
            // k가 2 이상인 경우
            // 문자열의 모든 문자들을 정렬하여 사전 순으로 가장 작은 문자열을 만듦
            char[] chars = s.toCharArray(); // 문자열을 문자 배열로 변환
            Arrays.sort(chars); // 문자 배열을 정렬
            return new String(chars); // 정렬된 문자 배열을 문자열로 변환하여 반환
        }
    }
}

 

---

📚 풀이 보완

코드 설명

1. k == 1인 경우:
   • smallest 변수는 현재까지 발견한 사전 순으로 가장 작은 문자열을 저장합니다.
   • for 루프를 사용하여 문자열 s의 각 인덱스 i에 대해 회전된 문자열을 생성합니다.
     • **s.substring(i) + s.substring(0, i)**는 i번째 문자부터 끝까지의 부분 문자열과 처음부터 i번째 문자 전까지의 부분 문자열을 결합하여 새로운 회전된 문자열을 생성합니다.
   • if 조건문을 사용하여 현재 회전된 문자열이 smallest보다 작으면 smallest를 업데이트합니다.
   • 루프가 끝나면 smallest에는 가장 작은 문자열이 저장되므로 이를 반환합니다.
2. k >= 2인 경우:
   • **char[] chars = s.toCharArray()**는 문자열을 문자 배열로 변환합니다.
   • **Arrays.sort(chars)**는 문자 배열을 사전 순으로 정렬합니다.
   • **new String(chars)**는 정렬된 문자 배열을 새로운 문자열로 변환합니다.
   • 최종적으로 정렬된 문자열을 반환합니다.

---

📍 Plus+

풀이하면서 문제 이해도를 높여보는.. 나름 슈도코드... 

1 - 상세풀이

k == 1인 경우의 코드는 문자열을 여러 번 회전시키고, 회전된 문자열 중에서 사전 순으로 가장 작은 문자열을 찾는 과정입니다. 이를 이해하기 위해 substring과 compareTo 메서드를 설명 및 예제로 상세풀이

 

substring 메서드

substring 메서드는 문자열의 일부를 추출하는 데 사용됩니다.

• s.substring(i)는 s 문자열에서 i 번째 문자부터 끝까지의 부분 문자열을 반환합니다.
• s.substring(0, i)는 s 문자열의 처음부터 i 번째 문자 전까지의 부분 문자열을 반환합니다.

compareTo 메서드

compareTo 메서드는 두 문자열을 사전 순으로 비교합니다.

• s1.compareTo(s2)는 s1과 s2를 비교하여, s1이 s2보다 사전 순으로 앞에 있으면 음수를, 같으면 0을, 뒤에 있으면 양수를 반환합니다.

---

풀이

- 문자열 **s = "cba"가 주어지고 k = 1인 경우

1. 초기 상태:
   • smallest = "cba"
2. 첫 번째 회전 (i = 0):
   • rotated = s.substring(0) + s.substring(0, 0)
   • rotated = "cba" + ""
   • rotated = "cba"
   • **rotated.compareTo(smallest)**는 **"cba".compareTo("cba")**와 같고, 결과는 0입니다.
   • smallest는 그대로 **"cba"**입니다.
3. 두 번째 회전 (i = 1):
   • rotated = s.substring(1) + s.substring(0, 1)
   • rotated = "ba" + "c"
   • rotated = "bac"
   • **rotated.compareTo(smallest)**는 "bac".compareTo("cba")와 같고, 결과는 음수입니다 ("bac"가 "cba"보다 사전 순으로 앞에 있음).
   • smallest를 "bac"로 업데이트합니다.
4. 세 번째 회전 (i = 2):
   • rotated = s.substring(2) + s.substring(0, 2)
   • rotated = "a" + "cb"
   • rotated = "acb"
   • rotated.compareTo(smallest)는 "acb".compareTo("bac")와 같고, 결과는 음수입니다 ("acb"가 "bac"보다 사전 순으로 앞에 있음).
   • smallest를 "acb"로 업데이트합니다.
5. 종료:
   • 모든 회전이 완료되었으므로 최종적으로 smallest는 "acb"입니다.

결론

1. smallest를"cba"로 초기화합니다.
2. i = 0에서 rotated는 "cba"가 되고, smallest는 그대로 "cba"입니다.
3. i = 1에서 rotated는 "bac"가 되고, smallest를 "bac"로 업데이트합니다.
4. i = 2에서 rotated는 "acb"가 되고, smallest를 "acb"로 업데이트합니다.
5. 최종적으로 "acb"를 반환합니다.

이를 통해 k == 1인 경우의 동작 원리를 이해할 수 있습니다. 이 방법은 문자열을 가능한 모든 방법으로 회전시켜 사전 순으로 가장 작은 문자열을 찾는 방식입니다.

---

2 - 상세풀이

문자열을 문자 배열로 변환

char[] chars = s.toCharArray();

이 코드는 문자열 s를 문자 배열로 변환합니다. 예를 들어, s가 "baaca"라면, chars 배열은 ['b', 'a', 'a', 'c', 'a']가 됩니다.

 

문자 배열 정렬

Arrays.sort(chars);

Arrays.sort(chars)는 chars 배열을 사전순으로 정렬합니다.

이 메서드는 Java의 내장 메서드로, 배열을 정렬하는 데 사용됩니다. 위 예제에서는 ['b', 'a', 'a', 'c', 'a'] 배열이 ['a', 'a', 'a', 'b', 'c']로 정렬됩니다.

 

정렬된 문자 배열을 문자열로 변환

return new String(chars);

이 코드는 정렬된 문자 배열을 새로운 문자열로 변환합니다. 예제에서는 ['a', 'a', 'a', 'b', 'c'] 배열이 "aaabc" 문자열로 변환됩니다.

 

결론

예제 1: s = "baaca", k = 3

1. 문자 배열로 변환:
2. char[] chars = s.toCharArray(); // chars = ['b', 'a', 'a', 'c', 'a']
3. 문자 배열 정렬:
4. Arrays.sort(chars); // chars = ['a', 'a', 'a', 'b', 'c'
5. 문자 배열을 문자열로 변환:
6. return new String(chars); // 결과: "aaabc"

위 과정은 k >= 2일 때, 가능한 모든 문자 조합을 정렬하여 사전순으로 가장 작은 문자열을 만드는 데 사용됩니다. 이는 k가 2 이상일 때 문자열의 문자들을 자유롭게 이동

Arrays.sort 메서드는 Java에서 배열을 정렬하는 가장 기본적이고 효율적인 방법 중 하나로 내부적으로 빠른 정렬 알고리즘을 사용하여 배열을 정렬합니다