[Boj_10972] 다음 순열

📎 문제 링크

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

 

▸ 문제

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

N = 3인 경우에 사전순으로 순열을 나열하면 다음과 같다.

• 1, 2, 3
• 1, 3, 2
• 2, 1, 3
• 2, 3, 1
• 3, 1, 2
• 3, 2, 1

 

▸ 입력

첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄에 순열이 주어진다.

 

▸ 출력

첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.

 

📍 문제 정보

• 🥈  문제 레벨 : 실버 3
• 🔔  문제 유형 : 수학, 조합론
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

📍다음 순열(Next Permutation)

다음 순열이란, 현재 순열보다 사전순으로 바로 다음에 오는 순열을 의미한다.

 

예를 들어, 다음 순열을 구하고 싶은 순열이 다음과 같다고 해보자.

순열 : 7 2 3 6 5 4 1

 

이 순열에 대해 다음 순열을 구하는 과정은 다음과 같은 4단계로 이루어진다.

 

1️⃣ A[i-1] < A[i]를 만족하는 가장 큰 i 찾기

뒤에서부터 순열을 탐색하며 처음으로 감소가 멈추는 지점(i-1)을 찾는다.

즉, A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.

이는 뒤쪽에서부터 시작되는 내림차순 구간이 끝나는 지점을 의미한다.

7 2 3 6 5 4 1
      ▲
     i-1 = 2 (A[i-1] = 3), i = 3 (A[i] = 6)

 

2️⃣ j ≥ i이면서 A[j] > A[i-1]을 만족하는 가장 큰 j 찾기

i부터 순열을 끝까지 탐색하며, A[j] > A[i-1]을 만족하는 가장 큰 j를 찾는다.

이는 i ≤ j 조건을 만족하면서 A[j] > A[i-1]인 가장 큰 j를 찾는 것이다.

7 2 3 6 5 4 1
          ▲
         j = 5 (A[j] = 4), A[i-1] = 3

 

3️⃣ A[i-1]과 A[j]를 swap

찾은 두 값을 서로 교환한다.

Before swap: 7 2 3 6 5 4 1  
After swap : 7 2 4 6 5 3 1

 

4️⃣ A[i]부터 끝까지 오름차순 정렬 (뒤집기)

A[i]부터 끝까지의 구간은 원래 내림차순이었기 때문에,
해당 구간을 뒤집어서 오름차순으로 정렬하면 가장 작은 수열이 된다.

Before reverse: 7 2 4 6 5 3 1  
After reverse : 7 2 4 1 3 5 6

 

이렇게 4단계 과정을 거치면, 입력된 순열의 다음 순열을 얻을 수 있다.

 

만약 입력된 순열이 사전순으로 가장 마지막 순열이라면, 더 이상 다음 순열이 존재하지 않기 때문에 -1을 출력한다.

 

위 풀이의 코드를 바탕으로 전체적인 코드를 작성해 보면 아래와 같다.

 

✔ 코드

메모리 : 13432KB
시간 : 96ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine()); // 1부터 N까지의 수

        StringTokenizer st = new StringTokenizer(br.readLine());
        arr = new int[n]; // 순열
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        StringBuilder sb = new StringBuilder();
        if (nextPermutation()) {
            for (int a : arr) {
                sb.append(a).append(" ");
            }
        } else { // 사전순으로 마지막에 오는 순열
            sb.append(-1);
        }

        System.out.println(sb.toString());

        br.close();
    }

    private static boolean nextPermutation() {
        int i = arr.length-1;

        // A[i-1] < A[i]를 만족하는 가장 큰 i를 찾기
        while (i > 0 && arr[i-1] >= arr[i]) {
            i -= 1;
        }

        // i의 위치가 0이면 내림차순 (마지막 순열)
        if (i <= 0) return false;

        // j >= i이면서 A[j] > A[i-1] 을 만족하는 가장 큰 j를 찾기
        int j = arr.length-1;
        while (arr[i-1] >= arr[j]) {
            j -= 1;
        }

        // A[i-1]과 A[j]를 swap
        int tmp = arr[j];
        arr[j] = arr[i-1];
        arr[i-1] = tmp;

        j = arr.length-1;
        // A[i]부터 순열 뒤집기
        while (i < j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i += 1;
            j -= 1;
        }

        return true;
    }
}

 

처음엔 모든 경우의 수를 구하고 입력값과 동일한 경우의 수가 나오면 출력하면 되겠다 생각했는데,

이런 방식으로 해결하면 시간 초과 또는 메모리 초과가 발생할 것 같다는 생각이 들었다.

그러다 다음 수열을 구하는 방법이 있다는 것을 알게 되었고, 이를 활용해서 문제를 해결하고 공부한 내용을 정리할 겸 포스팅하게 되었다. 오늘도 이렇게 새로운 것을 하나 알게 되었다 ! @,@