[백준] 10972번 - 다음 순열 (!) (JAVA)

[백준] 10972번 - 다음 순열 (!) (JAVA)

 

---

[접근 방법]

 

처음 생각한 방법은 <N과 M 시리즈> 문제 처럼 DFS를 사용하여 만든 순열을 List에 저장하고,

List를 탐색하여, 주어진 순열의 다음 차례에 오는 순열을 찾아내면 된다고 생각했다.

그러나 이러한 방법을 사용하는 경우 "메모리 초과" 가 발생한다.

 

여러 사람의 풀이를 참고하여 종합한 방법은 다음과 같다.

<입력값>

10

4 6 2 7 9 8 5 3 1

 

1. 주어진 배열에서 마지막 원소를 마지막으로 하는 가장 긴 감소수열을 찾는다.

(arr[i-1] < A[i] 를 만족하는 가장 큰 i 찾기)

 

[4, 6, 2, 7, 9, 8, 5, 3, 1]

=> i = 4

 

2. j >= i 이면서, arr[j] > arr[i-1]을 만족하는 가장 큰 j 찾기

 

[4, 6, 2, 7, 9, 8, 5, 3, 1]

arr[i-1] = 7

arr[j] = 8

=> j = 5

 

3. arr[i-1] 과 arr[j]를 SWAP

[4, 6, 2, 7, 9, 8, 5, 3, 1]

[4, 6, 2, 8, 9, 7, 5, 3, 1]

 

4. arr[i] ~ arr[N-1] 까지 순열을 뒤집는다.

[4, 6, 2, 8, 1, 3, 5, 7, 9]

 

완성된 수열 [4, 6, 2, 8, 1, 3, 5, 7, 9]

 

 

+) 마지막 원소를 포함하는 가장 긴 감소수열 9, 8, 5, 3, 1 은 5개의 원소로 만들 수 있는 마지막 순열이다.

즉, 다음 순열을 구하기 위해서는 바로 앞 자리 수인 "7" 을 바꾸어야 다음 순열로 넘어갈 수 있다.

---

[JAVA 코드]

// 10972번 - 다음 순열
import java.util.*;
import java.io.*;

public class Main {


    public static void main(String[] args) throws IOException {
    
        // 0. 입출력 선언 / 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for(int i=0; i<N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        boolean flag = false;

        // 1. arr[N-1]을 마지막으로 하는 가장 긴 감소수열 찾기
        int idx = arr.length - 1;
        while(idx > 0 && arr[idx-1] >= arr[idx]){
            idx = idx - 1;
        }

        // idx == 0 : arr = 내림차순
        if(idx == 0){
            bw.write("-1" + "\n");
            flag = false;
        }
        // 마지막 순열이 아님
        else {
            flag = true;

            int j = arr.length - 1;

            // 2. idx <= j 이고, arr[j] > arr[i-1]인 가장 큰 j 찾기
            while(arr[idx-1] >= arr[j]){
                j = j - 1;
            }

            // 3. SWAP(arr[idx-1], arr[j])
            int temp = arr[idx-1];
            arr[idx-1] = arr[j];
            arr[j] = temp;

            // 4. arr[idx] ~ arr[N-1] 순열 뒤집기
            int k = arr.length - 1;
            while(idx < k){
                temp = arr[idx];
                arr[idx] = arr[k];
                arr[k] = temp;
                idx = idx + 1;
                k = k - 1;
            }
        }

        // 5. 출력
        if (flag){
            for(int val : arr){
                bw.write(val + " ");
            }bw.write("\n");
        }

        bw.flush();
        br.close();
        bw.close();      
    }
}

---

[Rewind]

 

1. 어려웠던 점

- 접근 방법 자체를 이해 하는데 많은 어려움이 있었음.

 

2. 알게된 점

- 순열에 특징에 대한 한가지 지식을 얻음

 

3. 개선 방향

- 수학적 사고력에 대한 공부 필요.