"순열" + [백준] 10972 - 다음 순열(JAVA)

[문제]

출처 - https://www.acmicpc.net/problem/10972

10972번: 다음 순열

 

 

---

[문제 풀이 전]

순열의 정의 : 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다 (위키백과)

 

크기가 N인 수열이 서로 다른 순열은 총 N! 개가 있다.

 

모든 순열을 사전순으로 나열했을 때

A = { 1 , 2, 3 } 인 경우 사전 순은 다음과 같다.

• 1 2 3  <-- 첫 순열  [오름차순(비 내림차순)]
• 1 3 2
• 2 1 3
• 2 3 1
• 3 1 2
• 3 2 1  <-- 마지막 순열  [내림차순 (비 오름차순)]

BruteForce 문제에서 순서가 중요한 경우, N가지를 수행해야 하는데 순서만 바꿀 수 있는 경우 수열을 이용할 수 있다.

---

[문제 풀이]

Next Permutation - 사전순으로 다음에 오는 순열을 찾는 방법

 

ex ) 순열 : 7 2 3 6 5 4 1

 

• 1.  A[i-1] < A [i]를 만족하는 가장 큰 i를 찾는다.
  • 즉, 순열의 마지막 수에서 끝나는 가장 긴 감소 수열(내림차순)을 찾아야 한다.

 ---> 7 2 3 6 5 4 1    //  6 5 4 1 로 가장 긴 감소하는 수열이 만들어진다.  A [i-1] = 3,  A [i] = 6  

 

• 2.  j >= i 이면서 A[j] > A [i-1]을 만족하는 가장 큰 j를 찾는다.
  •  A[i-1] 보다 큰 수 중 가장 작은 수 A [j] = 4

 ---> 7 2 3 6 5 4 1

 

• 3. A[i-1]과 A [j]를 swap 한다.
  •  A[i-1] = 3,  A [j] = 4  

 ---> 7 2 4 6 5 3 1

 

• 4. A[i] 부터 순열을 뒤집는다.
  • A [i] = 6

---> 7 2 4 1 3 5 6

 

4단계의 순서대로 진행하면 다음 순열을 찾을 수 있다.

---

[소스 코드]

 

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(br.readLine());
		int a[] = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<n; i++) {
			a[i] = Integer.parseInt(st.nextToken());
		}
		
		if(next_Permutation(a)) {
			for(int val : a) {
				sb.append(val).append(" ");
			}
		}else {
			sb.append("-1");
		}
	
		System.out.println(sb);
	}

	public static boolean next_Permutation(int a[]) {
		int i = a.length-1;
		
		//1. A[i-1] < A[i] 를 만족하는 가장 큰 i를 찾는다.
		while(i > 0 && a[i-1] >= a[i]) {
			i -= 1;
		}
		
		//i의 위치가 0이면 내림차순(마지막 순열)
		if(i<=0) return false; 
		
		int j = a.length - 1;
		
		//2. j >= i 이면서 A[j] > A[i-1] 을 만족하는 가장 큰 j를 찾는다.
		while(a[i-1] >= a[j]) {
			j -= 1;
		}
		
		//3. A[i-1]과 A[j] 를 swap 한다.
		int temp = a[j];
		a[j] = a[i-1];
		a[i-1] = temp;
		
		j = a.length-1;
		
		
		//4. A[i] 부터 순열을 뒤집는다.
		while(i < j) {
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i += 1;
			j -= 1;
		}
				
		return true;
	}
}