[BOJ - JAVA] 10972 - 다음 순열

# 주소 

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

10972번: 다음 순열

 

# 문제

 

 

# 문제 해설 및 코드 리뷰

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

 

이번엔 BufferedReader로 입력 받아서 문제를 풀어야 했습니다.

(시간 초과가 난다는 소문이 많았기에...)

정수 N과 nums배열을 입력받고 mapToInt를 이용하여 String을 int형태로 변환시킵니다.

그리고 밑에 nextPermutation과 swap함수를 만들어 주도록 합니다. 

nextPermutation의 역할은 배열의 처음이 아닌 가장 마지막 위치로 가서 

nums[i]와 nums[i-1]의 크기를 비교하여 만약 nums[i-1]이 더 클경우 i의 값을 감소시키며 

서로의 크기를 비교합니다. 

즉, 1 2 4 3 이 있다면 4와 3을 비교했을 때 4가 3보다 더 크므로 i의 값을 감소시키고

2와 4를 비교한 뒤 이 때는 2가 4보다 작으므로 while문을 벗어나 i 의 값은 2가 저장됩니다.

그리고 nums[j]가 nums[j-1]보다 클 때의 상황도 생각해주어야 합니다.

만약 1 2 4 3 일경우 가장 마지막 원소를 비교했을 때 4 와 3을 비교하게 됩니다.

이 때 nums[j] < nums[j-1]일 경우에 j--를 하게 되는데,  4가 3보다 크므로

while문을 벗어나게 되고 swap문을 실행하게 됩니다. swap문은 그 해당 원소의 위치를 바꾸어 주는 것입니다.

따라서 i는 i-1해주어 1이고 j는 3이므로 2와 3의 위치를 바꿉니다. 그럼

1 3 4 2 가 됩니다.

이후, while문을 통해 i < j일 때 계속해서 i와 j를 이용하여 swap문을 실행하고 i값과 j값을 

증가, 감소시킵니다. 그럼 i는 원래 2이고 j는 3이었으므로 swap(2,3)이 실행되어 4와 2가 바뀝니다.

최종적으로 1 3 2 4가 만들어지게 되고 i 는 3, j는 2가되므로 while문에서 벗어나

return true를 출력하여 nextPermutation을 빠져나옵니다.

swap문 같은 경우에는 정말 많이 쓰는 기본 정렬 방법이니 알아주시면 좋겠습니다.

int temp = nums[a];

nums[a] = nums[b];

nums[b] = temp; 으로, 오른쪽에서 밑으로 대각선 사선모양끼리 같다고 학부생 시절에 

외웠웠는데 이게 생각보다 요긴한거같더라고요. 참고해주시면 좋겠습니다.