You are given a string s. Every letter in s appears once.
Consider all strings formed by rearranging the letters in s. After ordering these strings in dictionary order, return the middle term. (If the sequence has a even length n, define its middle term to be the (n/2)th term.)
Example
For s = "abc", the result should be "bac".
The permutations in order are:
"abc", "acb", "bac", "bca", "cab", "cba"
So, The middle term is "bac".
Input/Output
[input] string s
unique letters (2 <= length <= 26)
[output] a string
middle permutation.
처음 푼 풀이
모든 순열 뽑고 가운데 값 찾는다
4kyh 까지 퍼포먼스를 전혀 고려하지 않았는데
처음으로 타임아웃을 만났다.
public static List<String> generater(String input) {
List<String> reslut = new ArrayList<String>();
MiddlePermutation.permutation("", input, reslut);
return reslut;
}
private static void permutation(String chars, String input, List<String> result) {
if (input.isEmpty()) {
result.add(chars + input);
return;
}
for (int i = 0; i < input.length(); i++) {
permutation(chars + input.charAt(i), input.substring(0, i) + input.substring(i + 1), result);
}
}
public static String findMidPerm(String strng) {
// your code here!
List<String> result =MiddlePermutation.generater(strng);
Collections.sort(result);
return result.get((result.size() / 2) - 1);
}
성능을 고려해서 다시 짰다.
(1) 먼저 모든 순열을 구해 정렬 하는 것보다 문자를 정렬하는 것이 좋다.
(모든 순열을 구한 뒤 정렬 할 경우 문자열이 길어질 수록 정렬해야 할 순열이 많아진다. )
(2) 문자열이 짝수일 경우 중간에 있는 문자 + 나머지의 역순
(3) 문자열이 홀수일 경우 중간문자 + 나머지는 짝수이므로 (2) 를 다시한번 실행
홀수 일경우 불필요하게 정렬을 한번 더하고 있는데 오늘 생각보다 많은 시간을 소비해서 일단 넘어가자.
public static String findMidPerm(String strng) {
// your code here!
char [] temp = strng.toCharArray();
Arrays.sort(temp);
String sorted = new String(temp);
if(sorted.length()%2==0) {
int middle = sorted.length()/2-1;
StringBuilder remainder = new StringBuilder(sorted.substring(0,middle)+sorted.substring(middle+1));
return sorted.substring(middle,middle+1) + remainder.reverse().toString();
}else {
int middle = sorted.length()/2;
String remainder = sorted.substring(0,middle)+sorted.substring(middle+1);
return sorted.substring(middle,middle+1) + findMidPerm(remainder.toString());
}
}