[백준] 이전 순열

문제 주소

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

문제 설명

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 바로 이전에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

출력

첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.

예제 입력 1

4
1 2 3 4

예제 출력 1

-1

예제 입력 2

5
5 4 3 2 1

예제 출력 2

5 4 3 1 2

 

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int [] arr;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

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

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

        boolean smallest = false;
        int pivot = N-1;

        while(pivot>0 && arr[pivot-1] <= arr[pivot]){ //내림차순이 깨지는 pivot을 찾음(뒤에서부터 오름차순이 꺠지는)
            pivot--;
        }
        pivot--;

        if(pivot<0){
            smallest = true; //pivot이 0이거나 더 작다 -> 뒤에서부터 끝까지 오름차순이다 -> 더 작은것이 없다
        }else{
            int target = N-1;
            while(arr[pivot] <= arr[target]){ // pivot보다 더 작으면서 가장 오른쪽에 있는 것을 찾음
                target--;
            }

            //pivot과 target을 바꿈
            swap(pivot,target);

            //pivot+1 부터 순열을 뒤집음
            int i = pivot+1;
            int j = N-1;
            while(i<j){
                swap(j--,i++);
            }
        }

        if(smallest){
            sb.append(-1);

        }else{
            for(int t : arr){
                sb.append(t).append(" ");
            }
        }

        System.out.println(sb);
    }

    static void swap(int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

코드 설명

뒤에서부터 오름차순으로 보다가 첫번째 오름차순이 깨지는 순간 (그 전은 그게 가장 큰거다)

오른쪽에서 pivot 보다 더 작으면서 가장 오른쪽에 있는 것을 가져와서 (이게 가장 임팩트가 적다)

pivot과 바꿔준다!

그 후 pivot 오른쪽을 가장 크도록(내림차순이도록) 정렬한다

 

가장 적은 단위로 커져야 함 : 다음 순열

가장 적은 단위로 작아져야 함 : 이전 순열

다음 순열 문제와 정반대의 문제라 매커니즘이 비슷해서 이해가 잘 안 가시는 분은 다음 순열에 그림으로 설명한 것이 있으니 보는 것을 추천드립니다!

https://greedydeveloper.tistory.com/380

[백준] 다음 순열