알고리즘 | 조합론 | Java 백준[Silver III] 다음 순열 - 10972

[Silver III] 다음 순열 - 10972

문제 링크

성능 요약

메모리: 20068 KB, 시간: 224 ms

분류

조합론, 수학

제출 일자

2024년 9월 14일 02:22:06

문제 설명

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을 출력한다.

풀이

다음 순열을 구하는 알고리즘은 주어진 순열에서 사전순으로 다음에 오는 순열을 찾는 방식입니다. 이때, 주어진 순열이 사전순으로 가장 마지막 순열이라면 -1을 출력합니다.

전체 코드

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

public class Main {

    private static String solution(int size, int[] currentPermutation) {
        // 1. 뒤에서부터 탐색하여 첫 번째로 감소하는 위치(target) 찾기
        int target = -1;
        for (int i = size - 1; i > 0; i--) {
            if (currentPermutation[i - 1] < currentPermutation[i]) {
                target = i - 1;
                break;
            }
        }

        // 2. 마지막 순열일 경우 -1 리턴
        if (target == -1) {
            return "-1";
        }

        // 3. target 뒤에 있는 배열에서 target보다 큰 값 중 가장 작은 값을 찾기
        int swapIndex = size - 1;
        for (int i = size - 1; i > target; i--) {
            if (currentPermutation[target] < currentPermutation[i]) {
                swapIndex = i;
                break;
            }
        }

        // 4. target과 swapIndex의 값 교환
        swap(target, swapIndex, currentPermutation);

        // 5. target 이후 부분을 오름차순으로 정렬
        Arrays.sort(currentPermutation, target + 1, size);

        // 6. 결과를 StringBuilder로 만들어 리턴
        StringBuilder sb = new StringBuilder();
        for (int num : currentPermutation) {
            sb.append(num).append(" ");
        }

        return sb.toString();
    }

    private static void swap(int a, int b, int[] array) {
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }

    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 size = Integer.parseInt(br.readLine());
        int[] currentPermutation = Arrays.stream(br.readLine().split(" "))
            .mapToInt(Integer::parseInt)
            .toArray();

        bw.write(solution(size, currentPermutation));
        bw.flush();
        bw.close();
    }
}

알고리즘 단계

1. 뒤에서부터 탐색하여 첫 번째로 감소하는 위치(target) 찾기:

• 주어진 순열에서 오른쪽 끝부터 왼쪽으로 탐색하면서, 앞의 값이 뒤의 값보다 작은 첫 번째 위치를 찾습니다.
• 이 위치(target)는 교환이 필요한 지점입니다. 이때 target이 없으면 이는 이미 사전순으로 마지막 순열입니다.

예를 들어, 순열 1 2 3 4에서 3은 4보다 작으므로 target = 2 (인덱스)입니다.

2. 마지막 순열 처리:

• 만약 target이 없을 경우, 즉 내림차순(가장 마지막 순열)이면 더 이상 사전순으로 다음 순열이 존재하지 않으므로 -1을 반환합니다.
  예: 순열이 5 4 3 2 1이면 이는 마지막 순열이므로 -1을 출력합니다.

3. 교환할 값을 찾기:

• target 뒤에 있는 값들 중에서 target 값보다 큰 값 중 가장 작은 값을 찾습니다.
• 이 값을 swapIndex로 기록하고 target과 swapIndex의 값을 교환합니다.
  예: 1 2 3 4에서 target = 2이고, 4와 3을 교환하여 1 2 4 3으로 바꿉니다.

4. target 이후 배열을 오름차순으로 정렬:

• target 위치 이후의 배열을 오름차순으로 정렬합니다. 이는 사전순으로 다음에 오는 순열을 만들기 위함입니다.
  예: 1 2 4 3에서 target 이후의 부분은 이미 정렬되어 있으므로 그대로 두면 됩니다.

예시 1

입력:

4
1 2 3 4

• 3 < 4이므로 target = 2 (값: 3)
• 3과 4를 교환하여 1 2 4 3을 만듦.
• target 이후 배열은 이미 정렬된 상태이므로 그대로 유지.
• 결과: 1 2 4 3

예시 2

입력:

5
5 4 3 2 1

• 모든 값이 내림차순이므로 -1을 출력.

시간 복잡도

• O(N): 순열을 한 번 탐색하고, 이후 일부 배열을 정렬하는 과정에서 최악의 경우에도 O(N log N) 시간이 소요됩니다.