[BOJ - JAVA] 10973 - 이전 순열

# 주소

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

10973번: 이전 순열

 

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.*;
import java.io.*;
public class Main{
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N;
    static int[] nums;
    public static void main(String[] args) throws IOException{
        N = Integer.parseInt(br.readLine());
        nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        
        if(nextPermutation()){
            for(int i = 0; i < N; i++) {
                System.out.print(nums[i] + " ");
            }
            
        }else{
            System.out.println("-1");
        }
    }
    // 1 2 4 3 을 1 2 3 4로 바꾸어야함.
    private static boolean nextPermutation() {
        int i = nums.length - 1;
        while(i > 0 && nums[i-1] <= nums[i]){
            i--;
        }
        if( i <= 0) 
            return false;
        int j = nums.length - 1;
        while(nums[j] >= nums[i-1]){
            j--;
        }
        swap(i-1,j);
        // 1 3 2 4일 경우엔 1 2 4 3으로 바꿔야함.(1 3 4 2)
        // 1 4 2 3일 경우엔 1 3 4 2로 바꿔야함.
        j = nums.length - 1;
        while(i < j){
            swap(i,j);
            i++;
            j--;
        }
        return true;
    }
    private static void swap(int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

 

이전 문제 10972번과 아주 유사한 문제입니다. 부등호 방향을 조금 신경 써주시면 되겠습니다.

nums[i] >= nums[i-1]일 때 i--를 시행하여 i값을 저장합니다.

nums[j] >= nums[i-1]일 때 j--를 시행하여 j값도 마찬가지로 저장합니다.

그리고 swap문을 실행하여 i-1한 값과 j값을 비교하여 바꿉니다.

이후 i < j일 때 swap(i,j)를 시행하여 i와 j를 i < j가 만족할 때 까지 i++, j--를 시행합니다.

그리고 nums를 출력하면 되겠습니다만, 이전 문제에도 그렇고 이번에도 BufferedReader를 이용하여 풀었습니다.

(확실히 성능면에서 Scanner보다 뛰어나지만 빠른 코딩을 좋아하는 저에게 있어서 타자칠게 많은.... 건)

 

 

이전 문제에서 설명을 안드렸었는데 -1을 출력하려면 모든 차수가 오름차순일 때 가능합니다.

이 때 while문을 이용하여 nums[i] >= nums[i-1]일 때를 적용시킨다면 i--가 입력되어 i를 음수로 만들 수 있습니다.

따라서 return false를 만들고 출력할 때 nextPermutation이 false이면 -1을 출력하도록 유도하면 되겠습니다.

 

불평하지 않고 열심히 하겠습니다. 여러분들도 화이팅하세요!