백준 10972 다음 순열 (Java)

1. 문제 링크

10972번: 다음 순열

 

2. 문제 및 입출력예제

 

3. 문제 풀이

그냥 순열로 문제를 풀게 될 경우 N이 너무 커서 시간초과가 발생한다.

그래서 규칙을 찾는데 한참 걸렸다.. 온갖 방법을 총동원해서 찾은 규칙이다.

1. 항상 순열의 뒤에서부터 바뀌는 범위가 넓어진다.
   ex) 1 2 3 4 -> 1 2 3 4 -> 1 3 2 4 -> 1 3 4 2 -> 1 4 2 3 -> 1 4 3 2 -> 2 1 3 4
2. 뒤에서부터 오름차순을 확인하면서 처음으로 오름차순이 아닌 값(now)을 찾는다.
   만약 뒤에서부터 처음까지 전부 오름차순일 경우, 다음 순열은 없다.
3. 오름차순 중 now와 값을 바꿀 now보다 큰 수 중 가장 작은 값(now2)을 찾는다.
4. now와 now2 값의 위치를 바꾼다.
5. now값부터 문자열의 끝까지 내림차순으로 정렬한다.

 

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static int N;
	static int[] num; 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		String[] split = br.readLine().split(" ");
		num = new int[split.length];
		for(int i=0;i<split.length;i++) {
			num[i] = Integer.parseInt(split[i]);
		}
		if(permutation()) {
			for(int i=0; i<N; i++) {
				System.out.print(num[i]+" ");
			}
		}
		else {
			System.out.println("-1");
		}
	}
	private static boolean permutation() {
		int now = num.length-1; 
		while(now>0 && num[now-1]>num[now]) { 
			now--;
		}
		
		if(now==0) { 
			return false;
		}
		
		int now2 = num.length -1;
		while(num[now2]<num[now-1]) { 
			now2--;
		}

		int temp = num[now-1];
		num[now-1] = num[now2];
		num[now2] = temp;
		
		Arrays.sort(num, now, num.length);
		return true;
	}
}