[BOJ] 10972. 다음 순열(NextPermutation).java

#. Problem

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

* The copyright in this matter is in BOJ

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

NextPermutation 을 구현하는 문제이다.

#. Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class BOJ10972 {
 
    static int N, nums[];
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        N = Integer.parseInt(br.readLine());
        nums = new int[N];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++)
            nums[i] = Integer.parseInt(st.nextToken());
 
        if (nextPermutation()) {
            for (int i = 0; i < N; i++) {
                System.out.print(nums[i] + " ");
            }
        }
        else
            System.out.println("-1");
    }
 
    public static boolean nextPermutation() {
        int i = N - 1;
        while (i > 0 && nums[i - 1] >= nums[i]) i--;
        if (i == 0) return false;
 
        int j = N - 1;
        while(nums[i-1] >= nums[j]) j--;
        
        swap(i-1, j);
        
        int k = N-1;
        while(i<k) swap(i++, k--);
        
        return true;
    }
    
    public static void swap(int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
 

line 33) 꼭대기 찾기

    자신보다 작은 수를 찾을 때까지 동작

line 34) 마지막 순열의 상태이면 다음 순열이 없음

line 37) i-1 위치와 교환할 다음 단계 큰 수를 뒷쪽에서부터 찾기

          자신보다 작은 수를 찾을 때까지 동작

          i-1보다 큰 j는 항상 존재(꼭짓점)

line 39) i-1위치의 값과 j 위치의 값 교환

line 42) i위치부터 맨 뒤까지 오름차순 정렬