[Algorithm] 10973 이전순열

이전순열, 다음순열 🗒️

우선 순열이란 ?

• 주어진 원소들을 특정 순서대로 나열한 모든 경우의 집합을 의미합니다.
  예를 들어, 숫자 1,2,3의 순열은 이와 같습니다요~

  123,132,213,231,312,321

그리고 N개의 숫자가 주어지면 순열의 갯수는 N!(팩토리얼) 입니다.
ex) N이 3개이면 3!= 6으로 6개입니다.

다음순열 알고리즘 단계✅

순열을 찾는 과정은 3단계로 구성할 수 있습니다.

Step 1

• 배열의 뒷쪽부터 탐색하면서 현재 숫자와 앞의 숫자보다 작은 지점 을 찾습니다. 이 지점을 증가하지 않는 지점 이라고 보고, 이 위치를 기준으로 순서를 변경할 준비를 합니다.

Step 2

• 증가하지 않는 지점에서 발견된 숫자(Arr[i-1]) 즉,3이랑 교환할 숫자를 찾습니다. 이를 위해 뒤에서부터 탐색 하며, Arr[i-1] 보다 큰 숫자를 찾고 교환을 합니다.

Arr = {1,4,5,3,2}

Step 3
증가하지 않는 지점 이후의 배열은 내림차순으로 되어 있으니, 이를 다시 오름차순으로 정렬을 합니다. 이 작업을 통해 가장 작은 순열을 만들고 다음 순열로 됩니다.

Index(증가하지 않은지점) 부터 정렬을 하게 되면
Arr = {1,4,2,3,5}

Java코드

public static boolean prevPlusArr(int[] arr){
	int i = arr.length - 1;
    
    // 1. 증가하지 않은 지점 찾기
    while(i > 0 && arr[i] <= arr[i-1]){
    	i--;
    }
    
    // i가 0까지 간다는건, 다음순열이 없는 마지막 순열이라는 의미
    if(i <= 0) return false;
    // 2. 교환할 값 찾기
    int j = arr.length - 1;
    while(arr[i-1] >= arr[j]){
    	j--;
    }
    // 3. 교환하기
    int temp = arr[i-1];
    arr[i-1] = arr[j];
    arr[j] = temp;
    
    // 4. 정렬
    j = arr.length - 1;
    while(i < j){
    	temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
    }
    
    return true;
}

이전순열 알고리즘 단계✅

그러면 이 문제인 이전순열은 어떻게 구할까요 ?! 다음 순열의 반대로 생각하면 됩니다. 이것도 크게 3단계로 나눠서 볼 수 있습니다.

Step 1

• 배열의 뒷쪽부터 탐색하면서 현재 숫자와 앞의 숫자보다 작은 지점 을 찾습니다. 이 지점을 감소하지 않는 지점 이라고 보고, 이 위치를 기준으로 순서를 변경할 준비를 합니다.

Step 2

• 감소하지 않는 지점에서 발견된 숫자(Arr[i-1]) 즉,4랑 교환할 숫자를 찾습니다. 이를 위해 뒤에서부터 탐색 하며, Arr[i-1] 보다 큰 작은 값을 찾고 교환합니다.

Arr = {1,3,5,2,4}

Step 3
감소하지 않는 지점 이후의 배열을 오름차순으로 정렬하여 더 작은 순열을 만듭니다.

Java코드

public static boolean prevArr(int[] arr){
	int i = arr.length - 1;
    
    // 1. 감소하지 않은 지점 찾기
    while(i > 0 && arr[i] >= arr[i-1]){
    	i--;
    }
   
    
    // 2. 교환할 값 찾기
    int j = arr.length - 1;
    while(arr[i-1] <= arr[j]){
    	j--;
    }
    
    // 3. 교환하기
    int temp = arr[i-1];
    arr[i-1] = arr[j];
    arr[j] = temp;
    
    // 4. 정렬하기
    j = arr.length - 1;
    while(i < j){
    	temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
    }
    
    return true;
    
}

전체 코드

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

class Main {

    static int[] arr, tempArr;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

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

        if (prevArr(arr)) {
            for (int num : arr) {
                System.out.print(num + " ");
            }
        } else {
            System.out.println(-1);
        }


    }

    public static boolean prevArr(int[] arr) {
        int i = arr.length - 1;

        // 1. 감소하지 않은 지점 찾기
        while (i > 0 && arr[i] >= arr[i - 1]) {
            i--;
        }

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

        // 2. 교환할 값 찾기
        int j = arr.length - 1;
        while (arr[i - 1] <= arr[j]) {
            j--;
        }

        // 3. 교환하기
        int temp = arr[i - 1];
        arr[i - 1] = arr[j];
        arr[j] = temp;

        // 4. 정렬하기
        j = arr.length - 1;
        while (i < j) {
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }

        return true;

    }


}