[백준] 10972: 다음 순열 (자바/Java)

문제

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

10972번: 다음 순열

문제 풀이 

주어진 순열의 다음 순열을 구하기만 하면 된다. 

다음 순열을 구하는 방법은 다음과 같다. 

1. p[i-1] < p[i] 만족하는 가장 큰 i를 찾는다. 

2. j >= i 면서 p[j] > p[i-1] 만족하는 가장 큰 j를 찾는다.

3. p[i-1] 과 p[j] 를 swap한다.

4. p[i] 부터 순열을 뒤집는다. 오름차순으로. (i-1이 바뀌었으므로 i부터 재정렬 한다고 생각하면 됨)

 

코드

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

public class boj_10972 {
    // BufferedReader: 한 번에 모아서 전송됨
    // InputStreamReader: 입력 통로
    // System.in: 시스템 입력
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int num;
    static int[] p;

    public static void main(String[] args) throws IOException {
        num = Integer.parseInt(br.readLine()); // 첫 줄 읽음
        p = new int[num]; // 입력한 순열 넣기 위한 배열 선언

        // 입력한 값을 공백 단위로 끊어서 st에 저장해놓음
        StringTokenizer st = new StringTokenizer(br.readLine(), " "); 
       
        for(int i = 0; i<num; i++) { // 두번째 줄 읽음
            // 공백으로 끊어놓은 st 하나씩 읽어서 입력 순열 저장
            p[i] = Integer.parseInt(st.nextToken()); 
        }

        // 다음 순열 함수 호출 (마지막 순열 값이면 -1 출력)
        if(nextPermutation()) {
        for(int i = 0; i<num; i++) {
            System.out.print(p[i] + " ");
        }} else {
            System.out.print("-1");
        }

        br.close();
    }

    public static boolean nextPermutation() {
        // 1. 뒤에서부터 p[i-1] < p[i] 인 i를 찾는다.
        int i = p.length-1; // 마지막 인덱스
        // 조건 만족 안 할 때 == p[i-1] < p[i] 인 가장 큰 i
        while(i > 0 && p[i-1] >= p[i]) i--;
     
        if(i <= 0)  return false;

        // 2. 다시 뒤에서부터 p[j] > p[i-1] 인 j를 찾음
        int j = p.length-1; // 마지막 인덱스
        // 조건 만족 안 할 때 == p[j] > p[i-1] 인 가장 큰 j
        while(j>=i && p[j] <= p[i-1]) j--;
        
        // 3. swap
        swap(i-1, j);

        // 3 5 2 4 1 -> 3 5 4 1 2
        // i는 4이고, j는 5일 때는 조건 만족 안 하므로 i가 3일 때 멈춘다. (j가 i보다 크거나 같을 때 가능)

        // 4. 오름차순 정렬
        // 다시 j에 마지막 인덱스를 대입
        // 오름차순 정렬 방법
        j = p.length-1;
        while(i < j) {
            swap(i, j);
            i++; 
            j--;
        }
        return true;
    }

    public static void swap(int idx1, int idx2) {
        int temp = p[idx1];
        p[idx1] = p[idx2];
        p[idx2] = temp;
    }
}