백준 10972 다음 순열

다음 순열 성공분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

256 MB

12079

5247

3789

44.904%

문제

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을 출력한다.

package algo;

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	
	
	int num = sc.nextInt();

	int arr[] = new int[num];

	for(int i = 0 ; i < arr.length; i++) {
		arr[i] = sc.nextInt();
	}
	
	int idx = -1;
	// 맨뒤부터 arr[i-1]<arr[i] 를만족하는 수를 찾는다.
	for(int i = arr.length-1 ; i >0 ; i--) {
		
		if(arr[i-1] < arr[i]) {
			
			idx = i;
			break;
		}

	}

	if(idx == -1) {
		System.out.println(-1);
		
	}else {
		
		for(int i = arr.length-1; i >= idx ; i--) {
			// 끝부터 idx까지 arr[i-1]<arr[i] 만족하는 수 arr[i-1] 즉 arr[idx-1] 보다 큰수를 찾고 두수의 위치를 바꾼다.
			if(arr[i] > arr[idx-1]) {
				int tmp = 0;
				tmp = arr[i];
				arr[i] = arr[idx-1];
				arr[idx-1] = tmp;
				break;
			}
		}

		// 이 바뀐 오른쪽 자리를 오름차순 정렬
		Arrays.sort(arr, idx, arr.length);
		
		for(int i = 0 ; i < arr.length;i++) {
			System.out.print(arr[i]+" ");
		}
		
	        
			
		}
	}
	

	
}

 

 

 

다음 순열의 규칙공식을 알면 쉽게 구현할수 있는 문제였지만 규칙을 몰라 한참 고민했다.

1. 먼저 맨뒤 의 수부터 차례로 맨뒤부터 arr[i-1]<arr[i]를 만족하는 수를 찾는다.

2. i를 idx로 놓고 idx끝부터 idx까지 arr[i-1]<arr[i] 만족하는 수 arr[i-1] 즉 arr[idx-1] 보다 큰수를 찾고 두수의 위치를 바꾼다.

3. 바뀐수 즉 idx 오른쪽 자리를 오름차순 정렬하여 출력한다.

4.제일 첫수즉 arr[0]이 가장 큰 경우는 내림차순이 완료된 수이므로 -1을 출력한다.