728x90
반응형
https://www.acmicpc.net/problem/10972
10972번: 다음 순열
첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다.
www.acmicpc.net
정말 쉽게 아래와 같이 next_premutation을 이용해서 하는 방법입니다.
|
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 (next_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();
}
|
처음에 풀떄는 위의 방식을 몰라 직접구현했습니다.
당연히 모든 순열을 구해서 그다음 값을 구하면 간단하지만 위의 문제는 N이 1000이므로
절대 백트래킹으로 할 수 없습니다.
그래서 현재 위치에서 가장 뒤에 두 개 숫자를 swap 해서 바꾸어 입력값보다 크면 그 값을 출력하면 되지만
그게 아니면 한 칸 더 앞으로 가서 두 개를 비교해서 swap 하는 방식인데
이렇게 바로 되는 경우도 있지만
2 1 4 3 인경우가 입력이면
2 1 3 4 다되어 작아지므로
그다음 수인 1 4에 대해서 swap을 진행
2 4 1 3 이 되면 현재 입력보다 큰 수가 되는데
여기서 바로 출력하면 안 되고
아까 1보다 다음으로 큰 수 1보다 인덱스가 뒤에 있는 4 3 중
3이 오도록 해서 1과 3의 위치를 swap 하고
2 3 4 1로 바꾸고 나머지 4 1을 오름차순으로 다시 정렬한 방식으로 하면 된다는 규칙을 찾고 적용하여
문제를 풀었습니다. 다음 순열의 경우 제가 구현한 알고리즘이 stl보다 빠른 걸 볼 수 있습니다.
아래 소스를 참고해주세요
|
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
|
#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];
}
}
int main(void) {
while (1) {
init();
int c = 0;
int idx = 1;
for (int i = N; i >= 1; i--) {
if (ret[idx++] == 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);
for (int y = i + 1; y <= N; y++) {
if (save[i] < save[y]) {
swap(save[i], save[y]);
sort(save + i + 1 + 1, save + N + 1);
break;
}
}
for (int j = 1; j <= N; j++)
{// 바꿨는데 큰수면 바로 출력
printf("%d ", save[j]);
}
printf("\n");
return 0;
}
}
}
}
return 0;
}
|
728x90
반응형
'알고리즘 모음집 > 알고리즘 (Algorithm)' 카테고리의 다른 글
| 백준 10819 차이를 최대로 (0) | 2019.07.23 |
|---|---|
| 백준 10973 이전 순열 (0) | 2019.07.23 |
| 백준 1525 퍼즐 (0) | 2019.07.23 |
| 백준 10974 모든 순열 (0) | 2019.07.23 |
| 백준 16137 견우와 직녀 (0) | 2019.07.23 |
댓글