[백준] S3 10972번 다음 순열 (JAVA)

문제 출처 - Baekjoon Online Judge

문제는 여기

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. Next Permutation을 사용해 순열을 구해준다.

2. 뒤에서 부터 탐색을 한다.

3. 현재 위치보다 이전 값이 작다면 다시 이전 위치들을 탐색한다.

4.  현재 값보다 이전 값이 크다면 서로 위치를 교환하고 사이 순열을 다 뒤집어준다.

[접근]

1. 순열을 구하면서 배열에 저장해주고 주어진 순열의 다음값이 있다면 해당 값을 출력하고 없다면 -1을 출력하려고 했었다.

2. 하지만 메모리 초과 혹은 시간 초과가 발생할 수 있을 거라는 생각을 하였다.

3. 검색을 하여보니 Next Permutation을 사용하면 된다는 것을 알게 되어 이를 사용하여 문제를 해결하였다.

[코드]

package BOJ_silver;

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

public class Main_S3_10972 {
	static int n;
	static int[] arr;

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

		n = Integer.parseInt(br.readLine());

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

		nextPermutation(arr);
	}

	// 넥퍼
	private static void nextPermutation(int[] arr) {
		int n = arr.length;
		boolean b = true;

		Loop1:
		for (int i = n - 1; i > 0; i--) {
			// 현재 위치보다 이전 위치의 값이 작다면
			if (arr[i - 1] < arr[i]) {
				// 이전 위치들을 탐색해
				for (int j = n - 1; j >= i; j--) {
					// 더 큰 값이 있다면 서로 위치 교환
					if (arr[j] > arr[i - 1]) {
						int temp = arr[j];
						arr[j] = arr[i - 1];
						arr[i - 1] = temp;
						
						int k = n - 1;
						// 다 뒤집는다
						while (i < k) {
							int temp2 = arr[i];
							arr[i] = arr[k];
							arr[k] = temp2;
							i++;
							k--;
						}
						
						b = false;
						// 반복문 탈출
						// 다음 순열을 구했으니까
						break Loop1;
					}
				}
			}
		}
		// 마지막일 경우
		if (b) {
			System.out.print(-1);
		} else {
			for (int i = 0; i < arr.length; i++)
				System.out.print(arr[i] + " ");
		}
		System.out.println();
	}
}