[백준] 10972번 다음 순열 (C++)

문제

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

10972번: 다음 순열

코드

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10000];

int main(){
  int n;
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> arr[i];
  }
  int criIdx = n;

  //규칙1
  for(int i=n-1; i>=1; i--){
    if(arr[i]>arr[i-1]){
      criIdx = i;
      break;
    }
  }
  if(criIdx==n){
    cout << -1;
    return 0;
  }
  
  //규칙2
  for(int i=n-1; i>=criIdx; i--){
    if(arr[i]>arr[criIdx-1]){
      swap(arr[i], arr[criIdx-1]);
      break;
    }
  }
  
  //규칙3
  sort(arr+criIdx, arr+n);
  
  for(int i=0; i<n; i++){
    cout << arr[i] << ' ';
  }
  return 0;
}

 

다른 풀이(next_permutation 사용)

#include <iostream>
#include <algorithm>

using namespace std;

int arr[10000];

int main(){
  int n;
  cin >> n;
  for(int i=0; i<n; i++){
    cin >> arr[i];
  }
  if(next_permutation(arr, arr+n)){
    for(int i=0; i<n; i++){
      cout << arr[i] << ' ';
    }
  }else{
    cout << -1;
  }
  return 0;
}

정리

백트래킹으로 모든 경우의 수를 구한 후 제한을 두어 문제를 해결하려고 했더니 시간초과가 나왔다. 이 문제는 규칙을 찾아서 풀어야 했다. 규칙은 다음과 같다.

ex)

1 2 4 6 5 3 → 1 2 5 3 4 6

1 3 6 5 4 2 → 1 4 2 3 5 6

 

1. 뒤에서부터 뒷숫자와 앞숫자를 비교해 나가다가 앞숫자가 뒷숫자보다 작은 경우를 찾는다. 이 경우에서 뒷숫자가 기준이 되는 수(arr[criIdx])이다.

2. 뒤에서부터 기준이 되는 수까지 탐색해나가다가 기준이 되는 수 앞에 있는 수(arr[criIdx-1])보다 큰 첫번째 수가 나오면 그것과 기준이 되는 수 앞에 있는 수(arr[criIdx-1])를 swap한다.

3. 기준이 되는 수를 포함한 뒤에 나머지 배열들을 오름차순으로 정렬한다.

 

다른 풀이로 algorithm 라이브러리에 next_permutation을 사용하는 방법이 있다.

참조

https://orubt.tistory.com/17

https://guiyum.tistory.com/29