[알고리즘 PS] 백준 10974번 모든 순열 자바 문제풀이

문제

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

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

문제 접근

지난 문제를 통해서 우리는 nextPermutation() 메서드를 구현하면서 다음 순열을 구하는 방법을 배웠다.

 

이번에는 다음 순열을 구할 수 있는 최대까지 구하는 모든 수열문제를 풀어볼 것이다.

 

이번 문제도 순열에 대한 핵심 컨셉에 대해 알고 있는지를 물어보는 것이기 때문에 nextPermutation() 만 구현할 수 있으면 쉽게 해결할 수 있는 그런 간단한 문제이다.

 

해결법

다음 순열을 구하기 위한 방법에는 다음 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] 부터 순열을 뒤집는다.

정답 코드

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();

        int[] arr = new int[n];

        for(int i = 0; i < n; i++) {
            arr[i] = i + 1;
        }

        do {
            for(int value : arr) {
                System.out.print(value + " ");
            }
            System.out.println();
        }while(nextPermutation(arr));

    }

    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 idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }
}

---

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