(Java) Project Euler 024 - Lexicographic Permutations

// A permutation is an ordered arrangement of objects.
// For example, 3124 is one possible permutation of the digits 1, 2, 3, and 4.
// If all of the permutations are listed numerically or alphabetically, we call it lexicographic order.
// The lexicographic permutations of 0, 1 and 2 are:

//  012     021     102     120     201     210

// What is the million lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9 ?

 

import java.util.Arrays;

public class ProjectEuler_024 {
    public static void main(String[] args) {
        int[] digits = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int count = 1_000_000;

        for (int i = 1; i < count; i++) {
            if (!nextPermutation(digits)) {
                break;
            }
        }

        // 배열을 문자열로 변환하여 출력
        System.out.println(Arrays.toString(digits).replaceAll("[\\[\\], ]", ""));
    }

    static boolean nextPermutation(int[] array) {
        int i = array.length - 1;
        while (i > 0 && array[i - 1] >= array[i]) {
            i--;
        }

        if (i <= 0) {
            return false;  // 마지막 순열이므로 다음 순열이 없음
        }

        int j = array.length - 1;
        while (array[j] <= array[i - 1]) {
            j--;
        }

        // i-1 위치와 j 위치의 값을 swap
        int temp = array[i - 1];
        array[i - 1] = array[j];
        array[j] = temp;

        // i 위치부터 끝까지 배열을 뒤집음
        j = array.length - 1;
        while (i < j) {
            temp = array[i];
            array[i] = array[j];
            array[j] = temp;
            i++;
            j--;
        }

        return true;
    }
}