Q10972 다음순열

 

 

 

기본값 이후의 배열을 비내림차순으로 만든 후 출력(순열)

가장 끝에서 부터 비교하는 이유: 처음 시작하는 순열의 최소값이여야 하므로

723/6541   3보다 큰수 : 6,5,4 중 가장 끝에 있는 수 선택 => 724/6531(O)

                                                                         => 726/5431 (X)

 

import java.util.Scanner;

public class Q10972 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int countNum = sc.nextInt();
        int[] permutationList = new int[countNum];

        for (int i = 0; i < countNum; i++) {
            permutationList[i] = sc.nextInt();
        }

        NextPermutation nextPermutation = new NextPermutation(permutationList);
        nextPermutation.printPermutation();


    }
}

class NextPermutation {
    private int[] permutationList;
    private int size;

    NextPermutation(int[] permutationList) {
        this.permutationList = permutationList;
        size = permutationList.length;

    }

    void printPermutation() {
        if (flagNextPermutation()) {
            for (int element : permutationList) {
                System.out.print(element + " ");
            }
        } else {
            System.out.println("-1");
        }

    }

    private boolean flagNextPermutation() {
    
     //1. a[i-1] < a[i] 를 만족하는 i를 찾는다.
     
        int i = size - 1;
        while (i > 0 && permutationList[i - 1] >= permutationList[i]) {
            i -= 1;
        }

        if (i <= 0) {
            return false;
        }
        
       //2.다시 j부터 j>=I 를 만족, a[j] > a[i-1]를 만족하는 첫번째 수
       
        int j = size - 1;
        while (permutationList[j] <= permutationList[i - 1]) {
            j -= 1;
        }
        
        //3. swap

        swap(i - 1, j);
        
        //4. 순열뒤집기

        j = size - 1;
        while (i < j) {
            swap(i, j);
            i++;
            j--;
        }
        return true;

    }

    private void swap(int i, int j) {
        int temp = permutationList[i];
        permutationList[i] = permutationList[j];
        permutationList[j] = temp;
    }


}

 

* 참고자료 : https://dundung.tistory.com/58

백준 10972 이전 순열 & 10973 다음 순열 Java