[백준][10972번] 다음 순열

문제 URL

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

나의 풀이

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        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());

        //(1)번과정
        int j = n - 1;
        while (j>0 && arr[j - 1] >= arr[j])
            j--;
        if(j <= 0){
            System.out.println(-1);
            return;
        }

        //(2)번과정
        int k = n - 1;
        while (arr[j - 1] >= arr[k] && k > (j - 1))
            k--;

        //(3)번과정
        int temp = arr[j - 1];
        arr[j - 1] = arr[k];
        arr[k] = temp;

        //(4)번과정
        for (int i = n - 1; j <= i; j++, i--) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i] + " ");
        }
        System.out.println(sb);
    }
}

느낀점

시간복잡도 다음 순열을 구하는 시간복잡도는 O(N) 전체 순열을 구하는 시간복잡도 O(N! * N)

풀이법

1. A[i-1] < A[i]를 만족하는 가장 큰i를 찾는다.
2. j>=i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다.
3. A[i-1]과 A[j]를 swap한다.
4. A[i]부터 순열을 뒤집는다.

• python과 c++은 다음 순열 구하는 라이브러리가 기본 제공되는데 java는 그렇지 않아서 너무 번거롭다.. 나중에 갈아타자