백준-10972번/다음 순열 (java)

 

문제 이해

 

수열을 입력받으면 사전순으로 다음에 오는 수열을 출력하면 된다.

 

만약 사전순으로 마지막 수열이면 -1을 출력한다.

 

문제 해결

 

ex)  7 2 3 6 5 4 1

 

1) 수열의 뒷 부분부터 오름차순인 부분의 끝을 찾아준다.(변수 count=3)

   7 2 3 6 5 4 1  

  ** 여기서 count가 0이면 사전순으로 마지막 번째 이므로 -1출력하고 종료

 

2) arr[count]부터 arr[N]까지의 원소 중 arr[count-1]보다 큰 가장 작은 원소를 찾아준다(변수 j=5)

   7 2 3 6 5 4 1

 

3) arr[count-1]와 arr[j] swap

  7 2 4 6 5 3 1 

 

5) arr[count]부터 arr[j]까지의 원소들을 거꾸로 뒤집어준다.

  7 2 4 1 3 5 6

 

<전체 코드>

import java.util.Scanner;

public class Problem10972 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int N= scanner.nextInt();
        int[] arr = new int[N];
        int count = N-1;
        int j=0;
        for(int i=0; i<N; i++){
            arr[i]=scanner.nextInt();
        }

        for(int i=N-1; i>0; i--){
            if(arr[i]<arr[i-1]){
                count--;
            }
            else{
                break;
            }
        }

        if(count==0){
            System.out.println("-1");
        }
        else{
           for(int i=count; i<N; i++){
               if(arr[count-1]<arr[i]){
                   j=i;
               }
           }
           int tmp=arr[j];
           arr[j]=arr[count-1];
           arr[count-1]=tmp;

           j=N-1;
           while(count<j){
               tmp=arr[count];
               arr[count]=arr[j];
               arr[j]=tmp;
               count+=1;
               j-=1;
           }

            for(int i=0; i<N; i++){
                System.out.print(arr[i]+" ");;
            }
        }


    }
}