<링크>
https://www.acmicpc.net/problem/10972
<소스코드>
|
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
|
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[10000];
int main()
{
int N;
scanf("%d", &N);
for (int i = 0; i < N; ++i)
scanf("%d", a + i);
int i = N - 1;
while (i > 0 && a[i - 1] > a[i])
--i;
if (i == 0)
{
printf("-1"); return 0;
}
int near = 10001;
int index;
for (int j = i; j < N; ++j)
{
if (a[i - 1] < a[j] && a[j] < near)
{
near = a[j];
index = j;
}
}
int tmp = a[i - 1];
a[i - 1] = a[index];
a[index] = tmp;
sort(a + i, a + N);
for (int i = 0; i < N; ++i)
printf("%d ", a[i]);
}
|
cs |
<풀이>
N이 10000이기 때문에 모든 순열을 하나하나 구해보면 N!의 시간이 걸리고 당연히 시간초과이다.그래서 하나하나 적어보며 규칙성을 찾았다.
1.
맨 뒤에서부터 시작해서 내림차순이 끊기는 지점을 찾아낸다.
1 2 3 4
1 2 4 31 3 2 41 3 4 21 4 2 31 4 3 22 1 3 42 1 4 32 3 1 4...3 4 2 14 1 2 3...4 3 2 1
2.
끊긴 지점에 있는 수가 증가되어야 하는데 조건이 있다. 앞에 나왔던 숫자는 제외하고, 뒤에 있는 숫자 중 크면서 가장 가까운 수로 바뀐다.
예를 들어보면
1이 증가되어야하는데 2로 될 수는 없다. 앞에 2가 있기 때문이다.
그럼 앞에 있는애들(2) 눈치 안보고 바뀔 수 있는 놈들은 뒤(4, 3)에 다 몰려있다.뒤에 있는 놈들 중에 누구로 바뀌면 될까 생각해봤는데 4로 바뀌면 안된다.2 1 x x 에서 바로 2 4 x x로 건너뛰는 셈이 되기 때문이다.
3으로 바뀌면2 3 x x 가 되고원래 뒤에있던 3의 자리에는 당연히 1이 들어가야한다. 즉, 맞바뀌게 된다. -> 2 3 4 1
3.
숫자를 맞바꾸고 나면 끊긴 지점 뒤로 오름차순 정렬을 해준다.3 뒤로 오름차순정렬을 해서 2 3 1 4를 만든다.
4.
끊긴 지점이 맨 앞이면, 맨 마지막 수열이므로 -1을 출력한다.
근데 사실 이런 고생을 안하고 풀수있는 방법이 있다. STL이 따로 있었다..
next_permutation( )
<소스코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
#include<stdio.h>
#include<algorithm>
using namespace std;
int a[10000];
int main()
{
int N;
scanf("%d", &N);
for (int i = 0; i<N; ++i)
scanf("%d", a+i);
if(next_permutation(a, a+ N))
for (int i = 0; i<N; i++)
printf("%d ", a[i]);
else printf("-1");
}
|
cs |
'알고리즘 풀이 > 기타' 카테고리의 다른 글
| 백준 13413 오셀로 재배치 (0) | 2018.08.01 |
|---|---|
| 백준 10973 이전 순열 (0) | 2018.07.24 |
| 백준 2725 보이는 점의 개수:: 들짐승 (0) | 2018.07.22 |
| 백준 9011 순서 :: 들짐승 (1) | 2018.07.22 |
| 백준 8982 수족관1 :: 들짐승 (0) | 2018.07.22 |