[알고리즘] 백준 이전 순열 10973번

2021/01/17 - [코딩/알고리즘] - [알고리즘] 백준 다음 순열 10972번 JAVA

[알고리즘] 백준 다음 순열 10972번 JAVA

 

www.acmicpc.net/problem/10973

10973번: 이전 순열

 

 

다음 순열 문제를 풀었다면 쉽게 풀 수 있는 문제

arry[i] 와 arry[i-1]의 부등호를 바꾸고

마지막에 내림차순으로 정렬

 

import java.util.Scanner;

public class Main_10973 {

	 public static int N;
	    public static int arry[];
	    
	    public static void main(String args[]) {
	    	Scanner scanner = new Scanner(System.in);
	    	
	        N=scanner.nextInt();
	        arry = new int[N];
	        
	        for(int i=0; i<N; i++){
	            arry[i] = scanner.nextInt();
	        }
	        scanner.close();
	        
	        if(sol()) output();   
	        else System.out.println("-1");
	        
	    }
	    public static boolean sol() {
	    	
	    	for(int i=N-1; i>=1; i--) {
	                if(arry[i] < arry[i-1]) {
	                    //arry[i-1] 이후 값 중 arry[i-1]이전 숫 찾는다.
	                    int num =fMin(arry,i-1,N-1);
	                    System.out.println(num);
	                    
	                    //num==0이면 이미 내림차순으로 정렬되어있다는 
	                    if(num==0) break;
	                 
	                    //찾은 수의 인덱스를 찾고 arry[i-1]와 바꿔준다.
	                    for(int j=i; j<N; j++) {
	                        if(arry[j]==num){
	                            int temp = arry[j];
	                            arry[j] = arry[i-1];
	                            arry[i-1] = temp;
	    
	                        }
	                    }
	                    sort_part(arry,i,N-1,false); //true:내림차순 false:오름차순
	                    return true;
	                }
	        }
	        
	        return false;
	    }
	 
	    public static int fMin(int arry2[], int start,int end) {
	       
	        int num=arry2[start];
	        sort_part(arry2,start,end,true);
	       
	        for(int i=start; i<=end;i++){
	            if(arry2[i]==num) {
	                return arry2[i-1];   
	            }
	        }
	        return 0;
	    }
	    
	    //결과출력
	    public static void output(){
	        for(int i=0; i<N; i++){
	            System.out.print(arry[i]+" ");
	            if(i == N-1) System.out.println("");
	            }
	    }
	    //배열의 일부분을 버블소트로 오름 차순 정렬
	    public static void sort_part(int ary[], int start, int end,boolean option) {
	    	
	    	for (int i=start; i<end;i++) {
	    		for(int j=i+1; j<=end;j++) {
	    			if(option) {
	    				if(ary[i] > ary[j]) {
	    					int temp=ary[i];
		    				ary[i]=ary[j];
		    				ary[j]=temp;
	    				}
	    			}
	    			else {
	    				if(ary[i] < ary[j]) {
	    					int temp=ary[i];
		    				ary[i]=ary[j];
		    				ary[j]=temp;
	    				}
	    				
	    			}