백준 10972 다음 순열

 

<링크>

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]); } Colored by Color Scripter

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( )

<소스코드>

#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");
}