백준 10972번 다음 순열

문제

나의 풀이

import java.util.*;

public class Main {
    public static boolean next_permutation(int a[]) {
        int i = a.length - 1;
        while(i > 0 && a[i - 1] >= a[i]) { // 1단계
            i -= 1;
        }
        
        if(i <= 0) { 
            return false;
        }
        
        int j = a.length - 1;
        while(a[j] <= a[i - 1]) { // 2단계
            j -= 1;
        }
        
        int temp = a[i - 1]; // 3단계
        a[i - 1] = a[j];
        a[j] = temp;
        
        j = a.length - 1;
        while(i < j) { // 4단계
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        if(next_permutation(a)) {
            for(int i = 0; i < n; i++) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
        } else {
            System.out.println("-1");
        }
    }
}

1. A[i-1] < A[i] 를 만족하는 가장 큰 i를 찾는다.
   즉, 순열의 마지막 수에서 끝나는 가장 긴 감소수열을 찾아야 한다.
2. j >= i면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다.
3. A[i-1]과 A[j]를 swap한다.
4. A[i]부터 순열을 뒤집는다.
   이런 단계를 거치는 다음 순열 함수를 구현해서 해결하면 된다.

결과

백준 10973번 이전 순열

문제

나의 풀이

import java.util.*;

public class Main {
    public static boolean prev_permutation(int a[]) {
        int i = a.length - 1;
        while(i > 0 && a[i - 1] <= a[i]) { // 1단계
            i -= 1;
        }

        if(i <= 0) {
            return false;
        }

        int j = a.length - 1;
        while(a[j] >= a[i - 1]) { // 2단계
            j -= 1;
        }

        int temp = a[i - 1]; // 3단계
        a[i - 1] = a[j];
        a[j] = temp;

        j = a.length - 1;
        while(i < j) { // 4단계
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }

        if(prev_permutation(a)) {
            for(int i = 0; i < n; i++) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
        } else {
            System.out.println("-1");
        }
    }
}

다음 순열에서 구현한 함수에서 부등호 방향들만 바꾸면 이전 순열을 구하는 함수가 된다.

결과

백준 10974번 모든 순열

문제

나의 풀이

import java.util.*;

public class Main {
    public static boolean next_permutation(int a[]) {
        int i = a.length - 1;
        while(i > 0 && a[i - 1] >= a[i]) { // 1단계
            i -= 1;
        }

        if(i <= 0) {
            return false;
        }

        int j = a.length - 1;
        while(a[j] <= a[i - 1]) { // 2단계
            j -= 1;
        }

        int temp = a[i - 1]; // 3단계
        a[i - 1] = a[j];
        a[j] = temp;

        j = a.length - 1;
        while(i < j) { // 4단계
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i += 1;
            j -= 1;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = i + 1;
        }

        do {
            for(int i = 0; i < n; i++) {
                System.out.print(a[i] + " ");
            }
            System.out.println();
        } while(next_permutation(a));
    }
}

다음 순열 함수의 리턴값이 true일 때 한번 for문을 돌리는 것이 아니라 do-while 문을 이용하여 리턴 값이 true인 동안 계속해서 동작하게 하면 된다.

결과