순열 활용하기

 

예제 입력 1

4

1 2 3 4

예제 출력 1

1 2 4 3

예제 입력 2

5

5 4 3 2 1

예제 출력 2

-1

 

https://www.acmicpc.net/problem/10972

10972번: 다음 순열

#include <stdio.h>
#define MAX_SIZE (10001)

int N;
int arr[MAX_SIZE];

void swap(int* ar, int a, int b)
{
	int temp = ar[a];
	ar[a] = ar[b];
	ar[b] = temp;
}


// 1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
// 2. j >= i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다.
// 3. A[i-1]과 A[j]를 swap한다.
// 4. A[i]부터 순열을 뒤집는다.
bool next_permutation(int* a, int n)
{
	int i = n - 1;
	while ((i > 0) && (a[i - 1] > a[i])) i--;

	if (i <= 0) return false;

	int j = n - 1;
	while ((i <= j) && (a[i - 1] > a[j])) j--;

	swap(a, i - 1, j);
	
	j = n - 1;
	while (i < j)
	{
		swap(a, i, j);
		i++; j--;
	}

	return true;
}

int main(void)
{
	scanf("%d", &N);
	
	for (register int i = 0; i < N; i++)
		scanf("%d", &arr[i]);

	if (next_permutation(arr, N))
	{
		for (register int i = 0; i < N; i++)
			printf("%d ", arr[i]);

		printf("\n");
	}
	else
		printf("-1\n");

	return 0;
}