[디폴트코드] Next Permutation

Next Permutation (NP)

• 순열을 보다 빠른시간에 작성하는 방법이다.
• 대표적인 문제로 다음수열(https://www.acmicpc.net/problem/10972)이 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
	static int[] array;
	static int Number;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		Number = Integer.parseInt(br.readLine());
		String[] tmm = br.readLine().split(" ");
		array = new int[Number];
		for (int i = 0; i < Number; i++) {
			array[i] = Integer.parseInt(tmm[i]);
		}
		next();		
	}
	
	// 다음 순열
	public static void next() {
		// 끝은 
		int i = Number-1;
		while( i>0 && array[i-1] > array[i]) {
			i -= 1;
		}
		if (i==0) {
			System.out.println("-1");
			return;
		}
		
		// 맨뒤에서 찾기 
		int j = Number -1;
		while ( array[j] < array[i-1]) {
			j -= 1;
		}
		
		//3
		swap(array, i-1,j);
		
		//4
		int k = Number-1;
		while(i<k) {
			swap(array, i,k);
			k -= 1;
			i += 1;
		}

		for(int x : array) {
			System.out.print(x + " ");
		}
		
		return;
	}
	public static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}

이전 순열

• 어떤 한 순열의 이전 것을 찾는 순열이다.
• https://www.acmicpc.net/problem/10973

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class D10_이전순열 {
	static int[] array;
	static int Number;
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		Number = Integer.parseInt(br.readLine());
		String[] tmm = br.readLine().split(" ");
		array = new int[Number];
		for (int i = 0; i < Number; i++) {
			array[i] = Integer.parseInt(tmm[i]);
		}
		
//		System.out.println(Arrays.toString(array));
		
		before();
		
	}
	
	// 이전
	public static void before() {
		// 끝은 
		int i = Number-1;
		while( i>0 && array[i-1] < array[i]) {
			i -= 1;
		}
		if (i==0) {
			System.out.println("-1");
			return;
		}
		
		// 맨뒤에서 찾기 
		int j = Number -1;
		while ( array[j] > array[i-1]) {
			j -= 1;
		}
		
		//3
		swap(array, i-1,j);
		
		//4
		int k = Number-1;
		while(i<k) {
			swap(array, i,k);
			k -= 1;
			i += 1;
		}

		for(int x : array) {
			System.out.print(x + " ");
		}
		
		return;
	}
    
	public static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}