μ΄μ μμ΄ (10973)
μ΄ λ¬Έμ λ μμ΄μ λν μ΄ν΄κ° νμν λ¬Έμ μ΄λ€.
μμ΄μ΄λ 1λΆν° NκΉμ§λ‘ μ΄λ£¨μ΄μ§ μμ΄μ λ§νλ©°, ν¬κΈ°λ νμ Nμ΄κ³ , κ²ΉμΉλ μκ° μ‘΄μ¬νμ§ μλλ€. Nμ΄ 5μΈ κ²½μ° μ μ λͺ¨λ μμ΄μ΄λ€.
μμ΄μ κ°κ° μ‘΄μ¬νλλ° λ¬Έμ μμ λ§νλ μ΄μ μμ΄ μ΄λ κ°μ μμ΄μ μ¬μ μμΌλ‘ λμ΄νμλ μ£Όμ΄μ§ μμ΄μ λ°λ‘ μ΄μ μμμ μμ΄μ λ»νλ€.
μλ₯Ό λ€μ΄ λ Nμ΄ 4μΈ κ²½μ° μ¬μ μμμ 첫 λ²μ§Έμ μμ΄ μ΄λ―λ‘ μ΄μ μμ΄μ΄ μκΈ° λλ¬Έμ -1
μ λ°ννλ©°, μ μ΄μ μμ΄μ μ΄λ€.
prev_permutation
c++μμλ prev_permutation
μ΄λΌλ μ΄μ μμ΄μ λ§λ€μ΄ μ£Όλ ν¨μλ₯Ό μ 곡νκΈ° λλ¬Έμ μ΄ λ¬Έμ λ₯Ό μ½κ² ν μ μμ§λ§, κ·Έλ κ² νλ©΄ μκ³ λ¦¬μ¦μ νΈλ μλ―Έκ° μκΈ° λλ¬Έμ, μ§μ λ§λ€μ΄ 보λκ² μ’λ€.
bool prev_permutation(int *a, int n)
{
int i = n - 1;
int j = n - 1;
while (i > 0 && a[i - 1] < a[i]) i--;
if (i <= 0) return false;
while (a[i - 1] < a[j]) j--;
swap(a[i - 1], a[j]);
while (i < j){
swap(a[i], a[j]);
i++;
j--;
}
return true;
}
μ΅μ’ μ½λ
#include <iostream>
#include <vector>
using namespace std;
bool prev_permutation(int *a, int n)
{
int i = n - 1;
int j = n - 1;
while (i > 0 && a[i - 1] < a[i])
{
i--;
}
if (i <= 0)
return false;
while (a[i - 1] < a[j])
{
j--;
}
swap(a[i - 1], a[j]);
while (i < j)
{
swap(a[i], a[j]);
i++;
j--;
}
return true;
}
using namespace std;
int main(){
int n, tmp, i=0;
cin >> n;
int a[10000]={0};
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
if(prev_permutation(a, n)){
for(int i = 0; i < n; i++){
cout << a[i] << " ";
}
}else{
cout << "-1";
}
return 0;
}