[Java]백준 10972 다음순열

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

 

1. 오른쪽에서 왼쪽으로 이동하면서 n과 n-1을 비교한다.

2. n-1 < n인경우를 찾는다. 찾은 인덱스를 기준으로 왼쪽 영역과 오른쪽 영역을 나눌 수 있다.

ex) 12543  --> 12 543

     123645987  --> 123645 987 

3. 해당 인덱스에 있는 숫자를 가지고 오른쪽 영역에서 오른쪽부터 왼쪽영역으로 움직이면서 크기를 비교한다.

4. 크다면 자리를 바꾼다.

5. 오른쪽영역의 숫자를 오름차순으로 정렬해준다.

 

글보다 숫자로 표기하면 더 이해하기 쉽다.

 

입력 : 326154

--> 3261 54  (영역 나누기)

--> 3261 54  (크기 비교하기)

--> 3264 51  (자리 바꾸기)

--> 3264 15  (오름차순 정렬)

출력 : 326415

 

 

10972번: 다음 순열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
//다음 순열
public class Baekjoon10972 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        
        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());
        }
        
        if (nextPermutation(arr)) {
            for (int i = 0; i < N; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        } else {
            System.out.println("-1");
        }
    }
    
    public static boolean nextPermutation(int[] arr) {
        
        //뒤에서부터 탐색하면서 a-1보다 a가 더 큰 경우 찾음
        int a = arr.length - 1;
        while(a > 0 && arr[a-1] >= arr[a]) a--;
        if (a <= 0 ) return false;
        
        //다시 뒤에서부터 탐색하며 a-1보다 b가 더 큰 경우 찾음
        int b = arr.length - 1;
        while(arr[a-1] >= arr[b]) b--;
        
        //a랑 b를 swap
        int tmp = arr[a-1];
        arr[a-1] = arr[b];
        arr[b] = tmp;
        
        //a에서부터 끝까지를 오름차순 정렬 
        int start = a;
        int end = arr.length - 1;
        while(start < end) {
            tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
            start++;
            end--;
        }
        return true;
    }
}