[백준 10973, Java] 이전 순열

문제

www.acmicpc.net/problem/10973

10973번: 이전 순열

 

풀이

alwaysbemoon.tistory.com/268 의 풀이와 반대로 생각하면 된다. 어떤 수열의 이전 수열을 구하기 위해서 @$% ---의 수열에서 @$% 으로 시작하는 첫번째 순열을 구한다. 그 다음 그 이전 수열은 ---에서 %보다 큰 수들 중 최소값과 %의 위치를 바꾼다. -%-에 대해 내림차순 정렬을 하면 @$-로 시작하는 마지막 수열을 구할 수 있다. 

 

 

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine().trim());
        Integer[] array  = new Integer[N];

        st = new StringTokenizer(br.readLine(), " ");
        for(int i =0; i<N; i++){
            array[i] = Integer.parseInt(st.nextToken());
        }

        Integer[] result = getResult(array);
        if(result[0] ==-1){
            bw.write("-1");
        }
        else{
            for(Integer num : result){
                bw.write(String.valueOf(num)+" ");
            }
        }
        bw.flush();


    }
    public static Integer[] getResult(Integer[] array){
        //@@@으로 시작하는 첫 순열구하기 -> 오름차순이 시작되는 인덱스 구하기
        int index = array.length-1;

        while(index>0){
            if(array[index-1] < array[index]){
                --index;
            }
            else{
                break;
            }
        }

        if(index==0){
            array[0] = -1;
            return array;
        }
        else if(index ==array.length-1){
            int temp = array[index];
            array[index] = array[index-1];
            array[index-1] = temp;
            return array;
        }
        else{
            //array[index-1]의 값보다 작은 수 중에서 최댓값이 있는 인덱스
            int tempIndex = array.length-1;
            while(tempIndex>=index){
                if(array[tempIndex]> array[index-1]){
                    --tempIndex;
                }
                else{
                    break;
                }
            }

            //tempIndex의 위치와 index-1 의 위치 바꾸기
            int temp = array[tempIndex];
            array[tempIndex] = array[index-1];
            array[index-1] = temp;

            //index~ N-1까지 내림차순 정렬
            Arrays.sort(array,index,array.length, Collections.reverseOrder());
            return array;
        }
    }
}