BOJ_10972 : 다음 순열

👉 문제링크

10972번: 다음 순열

---

---

🔸 문제 분석 🔸

• 순열의 수 n과 순열이 입력된다.
  • 순열을 사전 순으로 정렬했을 때, 입력 된 순서의 다음 순서인 순열을 출력한다.
• n이 1만까지 입력되므로, 재귀 메소드를 이용해 사전순 정렬을 구현하면 시간초과가 난다. (1만 팩토리얼..?)
• 사전 순 정렬은 다시 말하면 순열에서 내림차순 정렬이다.
  • 순열이 [1, 2, 3, 6, 5, 4]이라고 가정하면, 123654 다음으로 큰 수를 찾아야 한다.
  • 654만 봤을때 해당 조합에서 가장 큰 수이다.(내림차순)
  • 그 다음수를 찾으려면 내림차순이 아니게 되는 3을 바꿔야 한다.
    • 만약 이미 내림차순이라면 -1을 출력한다. (문제 조건의 사전순의 마지막 순열)
  • 6,5,4 중 3보다 크면서 최소값은 4이다.(swap : 124653)
  • 뒤에 남은 653을 오름차순으로 바꾸면 바로 다음 순열이 된다. (124356)
    • 오름차순으로 바꿀 때 3과 4를 바꿨어도 뒤에 653중 3은 최소값이 되므로 내림차순 상태이다.
  • 바로 다음 순열 을 출력한다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    static int[] arr;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        if (next_Permutation()) {
            for (int i : arr) {
                System.out.print(i + " ");
            }
        } else {
            System.out.println(-1);
        }
    }

    private static boolean next_Permutation() {
        int i = arr.length - 1;
        while (i > 0 && arr[i - 1] >= arr[i]) { // 1
            i--;
        }
        if (i == 0) {
            return false;
        }

        int j = arr.length - 1;
        while (arr[i - 1] >= arr[j]) {		// 2
            j--;
        }

        swap(i - 1, j);

        j = arr.length - 1;
        while (i < j) {				// 3
            swap(i, j);
            i++;
            j--;
        }
        return true;
    }

    private static void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

🔸 코드 해석 🔸

• 1) 인덱스 i를 순열 끝에서부터 0까지 바꿔가며 내림차순이 아닌 부분을 찾는다.
  • i가 0이 될 때까지 내림차순이면, 이미 내림차순 순열이므로 -1을 출력한다.
• 2) 인덱스 j를 순열 끝에서부터 i까지 바꿔가며 arr[j]가 arr[i-1]다 큰 경우를 찾는다.
  
  • i-1 뒤쪽의 내림차순에서 i-1보다 큰 수 중 가장 작은 값을 찾는 것이다.
  • 찾은 j인덱스의 값을 i-1인덱스의 값과 교환한다.
• 3) i-1 뒤쪽의 내림차순을 오름차순으로 바꾼다.
  • 처음과 끝 인덱스가 중앙에서 만날 때 까지 앞/뒤를 교환하면 오름차순이 된다.(==순열을 뒤집는다)

🔸 오답 코드 🔸

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
    static int[] arr;
    static Integer[] last;
    static boolean print = false;

    private static void dfs(ArrayList<Integer> temp) {
        if (temp.size() == arr.length) {
            boolean flag = true;
            if (print) {
                for (int i : temp) {
                    System.out.print(i + " ");
                }
                System.exit(0);
            } else {
                for (int i = 0; i < arr.length; i++) {
                    if (temp.get(i) != arr[i]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    print = true;
                }
            }
        } else {
            for (int i = 1; i <= arr.length; i++) {
                if (!temp.contains(i)) {
                    temp.add(i);
                    dfs(temp);
                    temp.remove(temp.size() - 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        arr = new int[n];
        last = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
            last[i] = arr[i];
        }

        Arrays.sort(last, Collections.reverseOrder());

        boolean flag = true;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != last[i]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            System.out.println(-1);
        }
        else
            dfs(new ArrayList<>());
    }
}

• 사전식 정렬을 재귀 메소드로 구현했었다.
• 입력된 순열과 같은 순열을 찾으면, 바로 다음 순열을 출력한다.
• 예제는 통과하지만, 제출 시 시간초과가 난다.

---

🔸 end 🔸

• 사전식 정렬을 재귀 메소드로 구현해서 시간초과가 났다.
• 정답 코드의 3번 while문의 조건을 (i != j)로 해서, i가 j보다 커지고 배열의 범위를 벗어나서 런타임 에러가 났다.
• 재귀 메소드 방식이 시간초과가 나자 어떻게 접근해야 할 지 몰라서 정답 포스팅을 찾아보았다.
  • 사전식 정렬된 상태에 대해서 재귀 방식만 알았는데, 새로운 특성을 알게 되었다. (내림차순 찾기)
  • swap과 문제 풀이 메소드를 따로 구현하는게 더 깔끔한 코드가 되는 것 같다고 생각했다.