CodeWars 일백 번째 문제

Next bigger number with the same digits

public static long nextBiggerNumber(long n) {
    char[] s = String.valueOf(n).toCharArray();

    for (int i = s.length - 2; i >= 0; i--) {
        for (int j = s.length - 1; j > i; j--) {

            if (s[i] < s[j]) {
                char tmp = s[i];
                s[i] = s[j];
                s[j] = tmp;
                Arrays.sort(s, i + 1, s.length);

                return Long.valueOf(String.valueOf(s));
            }
        }
    }

    return -1;
}

• 100번째 문제만큼은 4kyu로 내가 풀고 싶었으나 애석하게도 풀지 못했다.
• 위의 코드는 Best 코드이다.
• 나는 처음 해당 숫자의 모든 경우의 수를 구하려고 했다. 즉, 완전탐색을 하려고 했는데 여기에 알맞지 않은 알고리즘이었다.
• 작은 수에 대해서는 성공했으나 long 같이 큰 숫자에서는 효율적이지 못했다.
• Best 코드의 경우 굉장히 간단했다. 맨 뒤에서 부터 앞에 숫자들을 비교한다. 그때 앞에 숫자보다 뒤의 숫자가 크다면 바꾸어주고 그 뒤에만 따로 정렬하면 되는 알고리즘이다.
• 예를 들어 1027면 다음 큰 숫자는 1072이다.
• 위의 알고리즘대로 하면 일단 7과 2를 비교한다. 뒤의 숫자인 7이 더 크므로 서로 바꾼다. 그럼 1072이가 된다.
• 1072이 다음 숫자를 계속해서 보자. 맨뒤의 숫자인 2와 앞에 숫자인 7를 비교하자. 7이 더 크므로 넘어간다. 그다음 2와 0을 비교한다. 그럼 2가 더 크므로 바꾼다. 1270이 되고 이때 7과 0까지 정렬을 한다.(오름차순)
• 그럼 최종 1207이 된다.
• 그 다음 또 큰수는 1270이 된다.
• 1270의 다음 큰수를 찾으면 일단 답은 1702이다.
• 0은 앞에 1,2,7보다 작으므로 아무런 일이 일어나지 않는다.
• 그 다음 앞에 7로 옮겨와서 7은 2보다 크므로 1720이 된다. 이때 2와 0을 정렬하면 1702가 된다.
• 이런 식으로 흘러간다.
• 후 멀고도 어렵다.