[백준] 자바 10972 다음 순열

문제

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

3
2 3 1

출력 1

3 1 2

 

입력 2

5
4 1 2 3 5

출력 2

4 1 2 5 3 

 

입력 3

7
2 3 1 4 7 6 5

출력 3

2 3 1 5 4 6 7 

---

접근

핵심은 nextPermutation(다음순열) 이론입니다.

해당 이론을 모르신다면 다른 곳에서 공부 후, 문제를 풀어보시기를 추천합니다.

(안 그러면 멀리 돌아가야 될 수도....)

 

간단히 설명드리면

순열을 뽑아내는 과정을 하나하나씩 수행하는 과정입니다.

예를 들면

1 2 3 -> np(nextPermutation) -> 1 3 2 -> np -> 2 1 3 ->...

 

이 np의 과정을 순서대로 과정을 써보겠습니다.

1. 배열 뒤에서 부터 계속 커지는 값 찾기.

ex) 2 3 1 있을 때 1부터 시작해서 계속 커지는 값의 종착점은 3(만약 1 2 5 4 3 이였다면 종착점은 5)

 

2. 종착점 앞에 배열 지정

ex) 2 3 1 에서는 2

 

3. (2)에서 지정한 값 보다 큰 값을 뒤에서 찾기

ex) 2 3 1에서 2보다 큰 값을 뒤에서부터 찾아보면 3

 

4. (2)의 값과 (3)의 값을 스왑

ex) 3 2 1

 

5. (1)에서 지정한 종착점부터 배열 끝까지 순서대로 스왑

여기서는 한 번만 하면 됨

ex) 3 1 2

 

---

코드

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

public class Main {
		static int N,arr[];
		public static boolean np() {
			int i = N-1;
			while(i>0 && arr[i-1] >= arr[i]) i--;
			
			if(i==0) {
				System.out.println(-1);
				return false;
			}
			int j = N-1;
			while(arr[i-1] >= arr[j]) j--;
			
			int temp = arr[i-1];
			arr[i-1] = arr[j];
			arr[j] = temp;
			
			int k = N-1;
			while(i<k) {
				temp = arr[i];
				arr[i] = arr[k];
				arr[k] = temp;
				i++;
				k--;
			}
			
			for(int v : arr) {
				System.out.print(v+" ");
			}
			return true;
		}
	    public static void main(String[] args) throws Exception {
	    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	        N = Integer.parseInt(br.readLine());
	        StringTokenizer st = new StringTokenizer(br.readLine());
	        arr = new int[N];
	        for(int i=0; i<N; i++) {
	        	arr[i] = Integer.parseInt(st.nextToken());
	        }
	        np();
	        br.close();
	        bw.flush();
	        bw.close();
	    }
	}

---

주의

nextPermutation부터 공부!