https://www.acmicpc.net/problem/10973
10973번: 이전 순열
첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
이전 순열은 아래와 같이 prev_mutation을 이용해서 아주 간단히 구현이 가능합니다 하지만
규칙을 찾아 하는 방법도 있으니 알아볼까요?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include<stdio.h>
#include<algorithm>
using namespace std;
int ret[10004];
int N;
void init()
{
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d", &ret[i]);
}
}
void sol() {
if (prev_permutation(ret+1, ret + N+1) == true) {
for (int i = 1; i <= N; i++) {
printf("%d ", ret[i]);
}
printf("\n");
}
else {
printf("-1\n");
}
}
int main(void) {
init();
sol();
}
|
그래도 간단히 설명해 드리겠습니다.
입력된 순열이 1 3 2 4라고 합시다
우선 2 , 4번의 숫자가 들어간 배열의 방을 swap을 합니다.
그러면 배열은 1 3 4 2 가 됩니다. 다음 순열이라면 다음 것이 많기 때문에
빠져나오면 되지만 이전 순열이기때문에 입력된 배열의 숫자보다 작아야 합니다.
그렇지 않기 때문에 다시 원위치로 복귀를 한후
다시 이번에는 3 과 2의 배열 방을 바꿉니다.
그렇게 된다면 1 2 3 4 가 됩니다. 이번에는 바꾼 수가 입력된 숫자보다
작기 때문에 여기서 1 3 2 4의 이전 순열이 되도록 바꿔줘야 합니다.
다시 첨에 받았던 순열에서 현재위치의 인덱스가 0 1 2 3이라면
1번 인덱스의 숫자보다 작은 숫자를 1번인덱스로 가져와야 이전 순열이 되기 때문에
우선 2번 3번인덱스의 숫자가 오름차순이 될 수 있게 정렬을 해줘야 합니다.
현재의 경우는 오름차순이지만 아닐수 있기 때문에 정렬을 해줍니다.
그렇게 해서 바로 1번 인덱스보다 작은 숫자를 뽑게 되면 이전 순열에 적합한 숫자 이기
때문에 그숫자의 인덱스와 1번 인덱스를 바꿔줍니다.
그러면 1 2 3 4가되게되는데 1 3 2 4의 이전은 1 2 4 3 이기 때문에
2번 3번인덱스를 내림차순이 될 수 있도록 해줘야 합니다.
그럼 그 부분에 대해서 다시 내림차순으로 정렬을 하게되면
1 2 4 3이되게 됩니다. 그런 식으로 다른 순열도 적용하면 아무리 N이 크더라도
제시간 안에 이전 순열을 구할 수 있습니다.
간단히 설명한다고 했는데 길어졌네요.
N이 10000가 최고 라서 절대 일일이 순열을 구하면 시간 초과가 나니
저와 같이 규칙을 일일이 찾아 구현을 하던지 이전순열함수를 익혀서 구현하시면 됩니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
#include<stdio.h>
#include<algorithm>
using namespace std;
int N;
int ret[10004];
int save[10004];
void init()
{
scanf("%d", &N);
for (int i = 1; i <= N; i++) {
scanf("%d", &ret[i]);
save[i] = ret[i];
}
}
bool cmp(int a, int b) {
return a > b;
}
int main(void) {
while (1) {
init();
int c = 0;
int idx = 1;
for (int i = 1; i <=N; i++) {
if (ret[i] == i) {
c++;
}
else break;
}
if (c == N) {
printf("-1");
return 0;
}
else {
for (int i = N - 1; i >= 1; i--) {
int j = i + 1;
swap(save[i], save[j]);// 바꿔보고
int ci = 1;
if (i - 1 != 0)ci = i - 1;
int sum_r = 0, sum_s = 0;
for (int ten = 1, y = N; y >= ci; y--, ten *= 10)
{
sum_r += ret[y] * ten;
sum_s += save[y] * ten;
}
if (sum_r < sum_s)
{
swap(save[i], save[j]);
}
else
{
swap(save[i], save[j]);
int num = save[i] + 1;
sort(save + i+1 , save + N + 1,cmp);
for (int y = i + 1; y <= N; y++) {
if (save[i] > save[y]) {
swap(save[i], save[y]);
sort(save +y, save + N + 1,cmp);
break;
}
}
for (int j = 1; j <= N; j++)
{// 바꿨는데 큰수면 바로 출력
printf("%d ", save[j]);
}
printf("\n");
return 0;
}
}
}
}
return 0;
}
|
오늘은 여기까지이고 이전순열의 경우 함수와 직접 규칙을 찾아 구현한 방법의 속도는 비슷하니
편하시는 방식대로 구현하시면 좋을것 같습니다.
딱딱한 글만 있는 자료를 보시느라 고생하셨습니다.
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 1248 맞춰봐 (0) | 2019.07.23 |
|---|---|
| 백준 10819 차이를 최대로 (0) | 2019.07.23 |
| 백준 10972 다음 순열 (0) | 2019.07.23 |
| 백준 1525 퍼즐 (0) | 2019.07.23 |
| 백준 10974 모든 순열 (0) | 2019.07.23 |
댓글