[BOJ10972/JAVA] 다음 순열

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

10972번: 다음 순열

 

문제

 

풀이

처음에는 순열 문제여서 dfs로 순열을 만든다음에 배열에 저장하고 그 배열의 다음 인덱스를 출력하려고 했으나 풀이방법이 단단히 잘못되었다. 

 

다른사람의 코드를 참고하니 애초에 값을 받은 다음에 받은 값에서 다음 순열이 무엇인지 배열의 원소를 바꾸면서 정렬해주는 식이다.

 

만약에 7 2 3 6 5 4 1 이라는 순열이 있다고 치자,

1. 맨 오른쪽 인덱스부터 시작해서 수열의 오름차순이 끝나는 지점을 찾는다. 이 말은 1부터 시작해서 하나씩 줄여나가면서 오름차순이 아닌 지점을 찾는다. 1 4 5 6 까지는 오름차순이나 3을 만나는 순간 오름차순이 끝난다.  ---> arr[i] > arr[i-1]

2. 그리고 다시 맨 오른쪽 인덱스부터 시작해서 3보다 큰 수를 찾는다. ----> arr[i-1] < arr[j]

3. 그리고 서로 자리(arr[i-1], arr[j])를 바꿔준다. 

여기까지 해주면 7 2 4 6 5 3 1 이라는 순열이 된다. 이 순열은 7 2 3 6 5 4 1 다음으로 올 수 있는 가장 큰 수이다.

4. 6(i)부터 내림차순으로 해준다. 

여기까지 하면 7 2 4 1 3 5 6 으로 바로 다음 순열이 된다.

 

이것을 어떻게 생각해내는지 ...ㅠㅠ 다들 존경스러울 따름

밑에는 이것을 구현한 코드이다.

 

코드

package Week15;

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

public class BOJ10972 {
	
	static int arr[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int 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());
		}
		
		if(nextPermutation()) {
			for(int i=0;i<n;i++) {
				System.out.print(arr[i]+" ");
			}
		}else {
			System.out.println("-1");
		}
		
	}
	
	static void swap(int i, int j) {
		int temp=arr[i];
		arr[i]=arr[j];
		arr[j]=temp;
	}
	
	
	private static boolean nextPermutation() {
	    int i = arr.length-1;
	    
	    while(i > 0 && arr[i-1] >= arr[i]) i--;
	    if(i <= 0) return false;

	    int j = arr.length-1;

	    while(arr[j] <= arr[i-1]) j--;

	    swap(i-1, j);
	    j = arr.length - 1;
	    while(i < j) {
	        swap(i, j);
	        i++;
	        j--;
	    }
	    return true;
	}



}