문제
1부터 N까지의 수로 이루어진 순열이 주어졌을 때, 사전순으로 바로 이전 순열을 구하라.
입력
첫째 줄에 N (1 ≤ N ≤ 10,000), 둘째 줄에 순열이 주어진다.
출력
이전 순열이 있으면 출력하고, 없으면 -1을 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 1 2 3 4 | -1 |
풀이
뒤에서부터 감소하는 지점을 찾고, 해당 위치를 적절한 값으로 교체한 후 나머지를 내림차순으로 채운다.
- 뒤에서부터 탐색하여
sequence[i] < sequence[i-1]인 위치 i를 찾는다 - i-1 위치에 넣을 수 있는 가장 큰 미사용 수(현재 값보다 작은)를 찾아 교체한다
- i 위치부터 끝까지를 남은 수 중 내림차순으로 채운다
- 감소 지점이 없으면 첫 번째 순열이므로 -1을 출력한다
핵심 아이디어: 이전 순열은 다음 순열의 역연산이다. 감소 지점을 찾아 한 단계 줄이고, 나머지를 가능한 가장 큰 순서(내림차순)로 채운다.
코드
package day499;
import java.io.*;
import java.util.*;
public class Day486BOJ10973이전순열 {
static int N;
static int[] sequence;
static boolean[] visited;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
sequence = new int[N + 1];
visited = new boolean[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= N; i++) {
sequence[i] = Integer.parseInt(st.nextToken());
visited[sequence[i]] = true;
}
StringBuilder result = new StringBuilder();
if (check()) {
for (int i = 1; i <= N; i++) {
result.append(sequence[i]).append(" ");
}
System.out.println(result);
return;
}
System.out.println(-1);
}
static boolean check() {
for (int i = N; i >= 2; i--) {
visited[sequence[i]] = false;
if (sequence[i] < sequence[i - 1]) {
visited[sequence[i - 1]] = false;
sequence[i - 1]--;
for (int j = sequence[i - 1]; j >= 1; j--) {
if (visited[j]) {
continue;
}
sequence[i - 1] = j;
break;
}
visited[sequence[i - 1]] = true;
visit(i);
return true;
}
}
return false;
}
static void visit(int idx) {
for (int i = N; i >= 1; i--) {
if (visited[i]) {
continue;
}
sequence[idx++] = i;
visited[i] = true;
}
}
}복잡도
- 시간: O(N)
- 공간: O(N)