백준 10972번: 다음 순열

문제 설명

• https://www.acmicpc.net/problem/10972
• 어떤 순열이 주어졌을 때 사전순으로 다음에 오는 순열을 구해야 합니다.

접근법

• 순열을 뒤에서부터 앞에 값과 비교했을 때 오름차순이 아닌 부분에서 값이 변경됩니다.

• 오름차순이 아닌 두 숫자의 인덱스가 i-1, i일 때

  • 0~i-2번째 숫자는 그대로 유지됩니다.
  • i-1번째 숫자는 i~N-1번째 숫자 중 현재 i-1번째 숫자보다 큰 숫자들 중 가장 작은 숫자와 바뀝니다.
  • 바뀐 숫자를 포함한 나머지 숫자들은 오름차순으로 뒤에 합쳐집니다.

• ex) 13542

  • 3과5에서 오름차순이 아니게 됩니다.
  • 앞에 1은 그대로 유지됩니다.
    • 1xxxx
  • 3이후의 5,4,2중 3보다 크면서 가장 작은 값인 4가 3의 자리에 오게 됩니다.
    • 14xxx
  • 나머지 3,5,2는 오름차순으로 정렬됩니다.
    위에서 3과 4가 바꼈기 때문에 여기서는 4가 아닌 3이 남은 숫자입니다.
    • 14235

정답

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		boolean[] v = new boolean[N+1];
		StringBuilder sb = new StringBuilder();
		for (int i = N-1; i >= 1; i--) {
			if(arr[i-1] < arr[i]){
				for (int j = 0; j < i-1; j++) {
					v[arr[j]] = true;
					sb.append(arr[j]+" ");
				}
				int minVal = Integer.MAX_VALUE;
				for (int j = i; j < N; j++) {
					if(arr[i-1] < arr[j]) {
						minVal = Math.min(minVal, arr[j]);
					}
				}
				v[minVal] = true;
				sb.append(minVal+" ");
				
				for (int j = 1; j <= N; j++) {
					if(v[j]) continue;
					sb.append(j+" ");
				}
				break;
			}
		}
		if(sb.length() == 0) {
			System.out.println(-1);
		}else {			
			System.out.println(sb.toString());
		}
		

		// Permu(N,0,new boolean[N], new int[N]);
		
	}
	
	// 순열 확인용
	public static void Permu(int N, int depth, boolean[] v, int[] answer) {
		if(depth == N) {
			System.out.println(Arrays.toString(answer));
			return;
		}
		
		for (int i = 0; i < N; i++) {
			if(v[i]) continue;
			v[i] = true;
			answer[depth] = i+1;
			Permu(N,depth+1,v,answer);
			v[i] = false;
		}
	}
}