99클럽 코테 스터디 8일차 TIL - 정렬

항해99 코테 스터디 8일차 문제인 LeetCode의 'Orderly Queue'는 주어진 문자열의 앞 k개의 문자 중 하나를 맨 뒤로 보내는 것을 반복했을 때 가장 빠른 문자열을 구하는 문제다. 난이도는 Hard이며 정렬을 통해 해결할 수 있다.

 

오늘의 문제 - 899번 Orderly Queue 문제 정보

문제 키워드

- Sort

난이도

- Hard

 

문제 요약

• 문자열 s와, 문자열 길이보다 작거나 같은 자연수 k가 주어진다.
• 연산 = (s의 앞부터 k번째 문자 중, 하나를 문자열의 맨 뒤로 보내기)
• 연산을 반복하여 만들 수 있는 사전순으로 가장 빠른 문자열을 구하여라. (연산 반복 횟수에 제한은 없다)

 

문제 풀이 과정  

• 매우매우 헤맸다. k개의 문자 중 뒤로 보낼 것을 고르는 규칙을 찾기 위해 이런 저런 방법을 사용했다.
  • 가장 사전순으로 빠른 알파벳부터 보내기
  • 뒤로 보냈을 때 사전순으로 빨라지는 경우인 알파벳을 보내기
  • 등등
• 그러나, k가 1이 아닌 이상 (2 이상이라면) 그냥 문자열을 정렬한 것이 정답이 되는 간단한 문제였다.
  • k가 2이상이라면, 연산을 무한히 적용할 수 있기 때문에 k만큼의 공간을 버퍼로 삼아 문자열을 정렬할 수 있기 때문이다.
• k가 1인 경우에는 문자열간의 순서를 바꿀 수 없으므로, 하나씩 뒤로 보내면서 가장 빠른 경우를 찾아야 한다.

코드

class Solution {
    public String orderlyQueue(String s, int k) {
        if(k==1) {
            List<String> strings = new ArrayList<>();
            strings.add(s);
            while(true) {
                String last = strings.get(strings.size()-1);
                String next = last.substring(1, last.length()) + last.substring(0,1);
                if (next.equals(s)) break;
                strings.add(next);
            }
            Collections.sort(strings);
            return strings.get(0);
        } else {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            return new String(chars);
        }
    }
}

• 시간복잡도: O(LlogL)
• 공간복잡도: O(L)

 

오늘의 학습 회고

새롭게 알게된 것

• 어제와 마찬가지로 문제가 어렵고 복잡하다면 문제를 단순화 하는 법을 연습해야 할 것 같다.