[JAVA]백준_10972_다음순열

문제링크

 

https://www.acmicpc.net/problem/10972

 

 

import java.util.Scanner;


public class Main_10972 {


	static int N;
	static int numbers[];
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		
		numbers = new int[N];
		for(int i=0;i<N;i++) {
			numbers[i] = sc.nextInt();
		}

		if(np()) {
			for(int i=0;i<N;i++)
				System.out.print(numbers[i]+" ");
		}
		else
			System.out.println(-1);
	}
	
	public static boolean np() {
		int i = N-1;
		while(i>0 && numbers[i-1]>=numbers[i]) --i;
	
		if(i ==0) return false;
		
		int j = N-1;
		while(numbers[i-1]>=numbers[j]) --j;  //꺽이는 값 찾은 후 제일 큰 값 찾기
		
		swap(i-1,j);
		int k = N-1;
		while(i<k)
			swap(i++,k--);
		
		return true;
	}
	
	private static void swap(int i,int j) {
		int temp = numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = temp;
	}
}

 

평소에 사용하던 대로 재귀를 사용해서 풀면 시간초과가 난다.

따라서 규칙을 찾아서 풀거나 해야한다. 나는 next permutation 으로 다음 순열을 찾는 것을 사용했다.

 

 이 부분은 현재 순열의 맨 뒤에서 부터 탐색을 하면서 바로 직전이 나보다 크거나 같으면 올라가면서 꼭대기를 찾는 것이다.

 

 만약 i ==0 이면 이미 순열의 맨 마지막에 도달한 것이니 false를 return 한다.

그리고 j를 통해서 꼭대기를 찾은 후 꼭대기 수 말고 제일 큰 수를 찾아준다 (swap하기 위해)

 

이렇게 swap을 한 후 정리해주면 된다. (내림차순을 오름차순으로)