[BOJ] 다음 순열, 이전 순열

순열(Permutation)

• 크기가 N인 수열은 총 N!개가 존재한다.
• 순열을 사전 순으로 나열했을 때, 첫 번째 순열은 오름차순, 마지막 순열은 내림차순이다.
• N = 3인 경우에 사전순은 다음과 같다.
• 123
• 132
• 213
• 231
• 312
• 321

 

 

[10972] 다음 순열

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

 

1. A[j-1] < A[i]를 만족하는 가장 큰 i를 찾는다.

 

2. j >= i이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다.

 

3. A[j-1]과 A[j]를 swap 한다.

 

4. A[j]부터 순열을 뒤집는다.

 

 

소스코드

 

import java.util.Scanner;

public class Main {

	public void go() {
		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 (next_permutation(a, n))
			print(a);
		else
			System.out.println(-1);
	}

	public boolean next_permutation(int[] a, int n) {
		int i = n - 1;
		while (i > 0 && a[i - 1] >= a[i]) {	// 1
			i -= 1;
		}
		if (i <= 0)
			return false;
		int j = n - 1;
		while (a[i - 1] >= a[j])	// 2
			j -= 1;
		swap(a, i - 1, j);	// 3
		j = n - 1;
		while (i < j) {	// 4
			swap(a, i, j);
			i += 1;
			j -= 1;
		}
		return true;
	}

	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Main main = new Main();
		main.go();
	}
}

 

 

[10973] 이전 순열

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

 

소스 코드

 

import java.util.Scanner;

public class Main {

	public void go() {
		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 (prev_permutation(a, n))
			print(a);
		else
			System.out.println(-1);
	}

	public boolean prev_permutation(int[] a, int n) {
		int i = n - 1;
		while (i > 0 && a[i - 1] <= a[i]) {
			i -= 1;
		}
		if (i <= 0)
			return false;
		int j = n - 1;
		while (a[i - 1] <= a[j]) {
			j -= 1;
		}
		swap(a, i - 1, j);
		j = n - 1;
		while (i < j) {
			swap(a, i, j);
			i += 1;
			j -= 1;
		}
		return true;
	}

	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Main main = new Main();
		main.go();
	}
}