[알고리즘 PS] 백준 10973번 이전 순열 자바 문제풀이

문제

해당 포스팅은 백준의 10973번 이전 순열 의 접근과 해결 방법을 설명한 글 입니다.
정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.

이 문제를 해결하기 위해 어떤 방식으로 접근해야 하는지를 먼저 생각해보자.

문제 접근

이번 문제는 순열을 구하기 위한 Prev Permutation을 구현하는 문제이다.

지난 10972번 다음 순열 문제와 같은 취지의 문제라고 할 수 있다.

STL 에서는 next_permutation과 prev_permutation 이 기본적으로 제공되어 그대로 사용하면 되지만, 자바에서는 이를 직접 구현해줘야 한다.

 

다음 순열을 구하기 위해서는 4가지 순서를 따라야 한다고 했는데, 이전 순열을 구하려면 다음 순열을 구하는 부등호의 반대만 해주면 된다.

1. A[i-1] < A[i] 를 만족하는 가장 큰 i를 찾는다.
2. j >= 1 이면서 A[j] > A[i-1]을 만족하는 가장 큰 j를 찾는다.
3. A[i-1] 과 A[j]를 Swap 한다.
4. A[i] 부터 순열을 뒤집는다.

위의 과정을 한 번 수행하면 현재 수열에서 바로 이전 순열을 찾을 수 있다.

 

이 과정을 더 이상 수행할 수 없을 만큼 반복한다면 모든 순열을 구하는 알고리즘이 된다.

정답 코드

private static boolean nextPermutation(int[] arr) {
    int i = arr.length-1;
    while(i > 0 && arr[i-1] <= arr[i]) i--;
    if(i <= 0) return false;

    int j = arr.length-1;

    while(arr[j] >= arr[i-1]) j--;

    swap(arr, i-1, j);
    j = arr.length - 1;
    while(i < j) {
        swap(arr, i, j);
        i++;
        j--;
    }
    return true;
}

private static void swap(int[] arr, int index1, int index2) {
    int temp = arr[index1];
    arr[index1] = arr[index2];
    arr[index2] = temp;
}

---

정답 소스 코드를 확인하시려면 solve url 에서 확인 가능합니다.