[99클럽 코테 스터디 8일차 TIL] LeetCode - 899. Orderly Queue

체감 난이도 = 상

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

문제 분석 및 설계

처음에는 예외 케이스를 잘 처리해야하는 구현문제로 접근했습니다.
그러다보니 로직이 복잡해졌고 오답이 해결되지 않아 꽤 헤맸습니다.

해설을 참고해 다시 풀었습니다.

이 문제는 k가 1일때와 2이상일 때로 나눌 수 있습니다.
우선, 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)입니다.

코드

class Solution {
    public String orderlyQueue(String s, int k) {
        StringBuilder sb = new StringBuilder();
        char[] temp = s.toCharArray();
        Arrays.sort(temp);
        String result = new String(temp);
        
        String s1 = s;
        
        if (k == 1) {
            String cal = s;
            for (int i = 0; i < s.length(); i++) {
                String str = "";
                str = s1.substring(1, s.length());
                str += Character.toString(s1.charAt(0));
                
                if (str.compareTo(cal) < 0) cal = str;
                s1 = str;
            }
            result = cal;
        }
        
        return result;
    }
}

코드 개선

조금 더 깔끔하게 짤 수 있습니다.

class Solution {
    public String orderlyQueue(String s, int k) {
        if(k>1){
            char tempArray[] = s.toCharArray();
            Arrays.sort(tempArray);
            return new String(tempArray);
        } else {
            String ans  = s;
            for(int i=0;i< s.length(); i++){
                s = s.substring(1) + s.substring(0,1);
                if(ans.compareTo(s) > 0){
                    ans = s;
                }
            }
            return ans;
        }
    }
}

공부한 사항

• 문자열 s 정렬

char tempArray[] = s.toCharArray();
Arrays.sort(tempArray);
return new String(tempArray);

• StringBuilder의 메서드
  insert(int offset, String str) : offset위치에 str을 추가한다.
  substring(int start, int end))
deleteCharAt(int index)
reverse() : 해당 문자 전체를 뒤집는다.

Replace(Char, Char)	
:이 인스턴스에서 발견되는 지정된 문자를 지정된 다른 문자로 모두 바꿉니다.

Replace(String, String)	
:이 인스턴스에서 발견되는 지정된 문자열을 지정된 다른 문자열로 모두 바꿉니다.

Replace(char oldChar, char newChar, int startIndex, int count);
:이 인스턴스의 부분 문자열(startIndex + (count - 1))에서 발견되는 지정된 문자를 지정된 다른 문자로 모두 바꿉니다.

Replace(string oldValue, string? newValue, int startIndex, int count);	
:이 인스턴스의 부분 문자열(startIndex + (count - 1))에서 발견되는 지정된 문자열을 지정된 다른 문자열로 모두 바꿉니다.

• String 객체(str)와 StringBuilder/StringBuffer 객체(sb)와 비교
  : str.contentEquals(sb) 값이 일치하면 true 반환. (주소 비교 x)
  -> 앞이 String객체이어야 한다.

• char배열 arr을 바로 String 으로 변환
  : String.valueOf(arr)

• char 타입 한글자 chr을 String으로 변환
  : Character.toString(chr)