다음순열

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
bool next_permutation(vector<int> &arr,int n)
{
  int i = n-1;
  while(i>=0 && arr[i]<= arr[i-1])
  {
    i -= 1;
  }
  if(i <= 0){
    return false;
  }
  int j = n-1;
  while(arr[j] <= arr[i-1])
  {
    j-=1;
  }
  swap(arr[i-1],arr[j]);
  sort(arr.begin()+i,arr.end());
  return true;
}
int main()
{
  int n;
  cin>>n;
  vector<int> arr(n);
  for(int i=0 ; i < n ; i++)
  {
    cin >> arr[i];
  }
  if(next_permutation(arr,n))
  {
    for(int i=0;i<n;i++)
    {
      cout<<arr[i]<<' ';
    }
  }
  else{
    cout<<"-1";
  }
}

풀이방법

사전순으로 다음으로 오는 순열을 구하는 문제


c++ STL을 사용하지 않고 문제를 풀어보았다.


ex) 1 2 4 3 이면 다음 순열은 1 3 2 4 이기 때문에 

벡터 arr인덱스에서 arr[i] > arr[i-1] 인 부분을 찾고

i보다 큰 인덱스이며 arr[i-1] 보다 큰 j를 구한뒤 swap

그다음 arr[i] 부분부터 sort함수를 통해 오름차순으로 정리해주었다.