899. Orderly Queue

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

Orderly Queue - LeetCode

 

1. 문제와 예제, 그리고 제약사항

 

You are given a string s and an integer k. You can choose one of the first k letters of s and append it at the end of the string..

Return the lexicographically smallest string you could have after applying the mentioned step any number of moves.

 

 

 

 

2. 문제풀이

 

문제를 해석하면 다음과 같다.

문자열 s가 주어진다. 그리고 숫자 k가 주어지는데 문자열 s에서 k번째 중 1~k번째에 해당하는 문자 하나를 선택해서  문자열 맨 뒤로 붙일 수 있다. 이러한 과정을 거친 후 사전순으로 정렬하는 문자열을 리턴하면된다. 

(늘 느끼는 거지만...문제 이해가 가장 어렵다...)

 

이 문제는 k가 1인 경우와 1이 아닌 경우로 구분하면 간단하게 풀이가 가능하다.

 

먼저 k=1인 경우를 살펴보자

예제 1번의 k=1인 케이스를 살펴 보면 cba 문자열 중 k가 1이므로 1번째 문자열만 선택이 가능하다.

처리 방법은 아래와 같다.

1) 첫번째 문자열 이후 추출한 문자열에 뒤에다가 첫번째 문자를 추출 후 문자열을 합치게 된다.
   ex) bac

2) 1번 과정의 문자열(bac)과 원래 문자열 (cba) 를 비교하여 1번 과정의 문자열이 사전순으로 앞서는 경우 기존 문자열 s에 저장한다.

3) 위의 과정을 문자열 s만큼 반복하여  최종 결과를 리턴한다.

 

이번에는 k가 1이 아닌 경우를 살펴보자

이 방법은 더욱 간단하다. 주어진 문자열 s를 간단하게 Array.Sort함수를 이용하여 정렬하면 끝이 난다.

 

이를 구현한 소스 코드는 아래와 같다.

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