백준-10973번/이전 순열 (java)

 

 

문제 접근

 

이 전에 풀었던 "다음 순열"과 풀이법이 비슷한 문제이다.

만약 사전 순으로 첫 번째 순열이면 -1을 출력하도록 한다.

 

문제 풀이

 

ex) 7 2 3 6 5 4 1

 

 

1)  배열의 끝 부터 뒤로 가면서 내림차순인 곳까지를 찾는다.

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

count = 6

 

2) count가 0, 즉 맨 첫번째 순열이라면 -1을 출력

if(count==0){
    System.out.println("-1");
}

 

3) count가 0이 아니라면, count부터 N-1까지의 숫자 중 count-1번째 숫자보다 작은것의 배열 인덱스(변수 j로 저장)를 찾아준다.

for(int i=count; i<N; i++){
    if(arr[count-1]>arr[i]){
        j=i;
    }
}

 

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

int tmp=arr[j];
arr[j]=arr[count-1];
arr[count-1]=tmp;

 

 

5) 맨 끝 부터 arr[count]까지의 원소들을 뒤집어준다.

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

 

<전체 코드>

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]+" ");
            }
        }


    }
}