백준 10973: 이전 순열(JAVA)

https://www.acmicpc.net/problem/10973

10973번: 이전 순열

이전에 풀었던 다음 순열 문제를 조금만 변형하면 되는 문제다. 전체적인 알고리즘 논리는 같다. 부등호 방향만 반대로 해주면 된다. 

import java.util.*;
public class Main {
	 public static void swap(int [] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
     public static boolean nextPermutation(int[] a) {
            int i = a.length-1;
            //뒤에서부터 a[i-1] > a[i]인 첫번째 부분을 찾는다.
            while (i > 0 && a[i-1] < a[i]) {
                i--;
                if(i==0) break;
            }

			//i가 0이면 위의 루프를 다 돌았다는 의미 = 이미 오름차순으로 정렬되어 있음
            if (i <= 0) {
                return false;
            }

			//a[i..last] 중 a[i-1]보다 작은 수를 뒤에서부터 탐색
            int j = a.length-1;
            while (a[j] >= a[i-1]) {
                j--;
            }
            
            //a[i-1]과 a[j]의 자리를 바꿈
            swap(a, i-1, j);
            
            //a[i..last]까지 내림차순 정렬
            j = a.length-1;
            while (i < j) {
                swap(a, i, j);
                i--; j++;
            }
            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 (nextPermutation(a)) {
                for (int i=0; i<n; i++) {
                    System.out.print(a[i] + " ");
                }
            } 
            else {
                System.out.println("-1");
            }
        }
}