10972번: 다음 순열

문제

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

• 입력: 첫째 줄에 N (1 ≤ N ≤ 10,000)이 주어집니다. 둘째 줄에 순열이 주어집니다.
• 출력: 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력합니다. 만약 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력합니다.

풀이: O(N) 시간 복잡도의 수학적 알고리즘 (Next Permutation)

N이 최대 10,000이므로 모든 순열을 생성하는 재귀(DFS) 방식은 사용할 수 없습니다. 현재 배열의 상태를 뒤에서부터 훑으며 단 한 번의 순회(O(N))만으로 다음 상태를 유추하는 알고리즘을 적용해야 합니다.

알고리즘 단계 분석

1. 피벗 지점(i) 찾기: 배열의 뒤에서부터 탐색하며, a[i-1] < a[i]를 만족하는 가장 큰 인덱스 i를 찾습니다. 이는 순열의 뒷부분에서 내림차순이 끊기고 오름차순이 시작되는 지점을 찾는 과정입니다. 만약 i ≤ 0이라면 현재 순열이 이미 마지막(내림차순)이므로 1을 출력합니다.
2. 교체 대상(j) 찾기: 다시 배열의 맨 뒤에서부터 탐색하며, 앞서 찾은 피벗 값인 a[i-1]보다 엄격히 큰 첫 번째 숫자 a[j]를 찾습니다.
3. 값 교환 (Swap): a[i-1]과 a[j]의 위치를 서로 바꿉니다.
4. 뒷부분 뒤집기 (Reverse): 인덱스 i부터 배열의 끝까지는 현재 내림차순 상태입니다. 이 구간을 뒤집어서 오름차순(가장 작은 사전순 상태)으로 만들면, a[i-1]보다 큰 수로 시작하는 가장 빠른 순열이 완성됩니다.

코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());

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

       // 다음 순열이 존재하면 결과 배열 출력, 없으면 -1 출력
       if (nextPermutation(a)) {
          for (int i = 0; i < n; i++) {
             bw.write(a[i] + " ");
          }
       } else {
          bw.write("-1");
       }

       bw.flush();
    }

    // 다음 순열을 생성하는 O(N) 알고리즘
    static boolean nextPermutation(int[] a) {
       int i = a.length - 1;

       // 1. 뒤에서부터 a[i-1] < a[i]를 만족하는 첫 번째 인덱스 i 탐색
       while (i > 0 && a[i - 1] >= a[i]) {
          i--;
       }

       // i가 0 이하이면 마지막 순열임을 의미
       if (i <= 0) {
          return false;
       }

       // 2. 뒤에서부터 a[i-1] < a[j]를 만족하는 첫 번째 인덱스 j 탐색
       int j = a.length - 1;
       while (a[j] <= a[i - 1]) {
          j--;
       }

       // 3. i-1과 j 위치의 값을 교환
       swap(a, i - 1, j);

       // 4. i부터 배열 끝까지를 뒤집어서 오름차순 상태로 만듦
       j = a.length - 1;
       while (i < j) {
          swap(a, i, j);
          i++;
          j--;
       }

       return true;
    }

    // 배열의 두 요소를 교환하는 메서드
    static void swap(int[] a, int i, int j) {
       int tmp = a[i];
       a[i] = a[j];
       a[j] = tmp;
    }
}

알고리즘 분류

수학 (Mathematics), 조합론 (Combinatorics), 구현 (Implementation)