이전 μˆœμ—΄ (10973)

(문제링크)

이 λ¬Έμ œλŠ” μˆœμ—΄μ— λŒ€ν•œ 이해가 ν•„μš”ν•œ λ¬Έμ œμ΄λ‹€.

μˆœμ—΄μ΄λž€ 1λΆ€ν„° NκΉŒμ§€λ‘œ 이루어진 μˆ˜μ—΄μ„ λ§ν•˜λ©°, ν¬κΈ°λŠ” 항상 N이고, κ²ΉμΉ˜λŠ” μˆ˜κ°€ μ‘΄μž¬ν•˜μ§€ μ•ŠλŠ”λ‹€. N이 5인 경우 1234512345와 5432154321은 λͺ¨λ‘ μˆœμ—΄μ΄λ‹€.

μˆœμ—΄μ€ N!N!κ°œκ°€ μ‘΄μž¬ν•˜λŠ”λ° λ¬Έμ œμ—μ„œ λ§ν•˜λŠ” 이전 μˆœμ—΄ μ΄λž€ N!N!개의 μˆœμ—΄μ„ μ‚¬μ „μˆœμœΌλ‘œ λ‚˜μ—΄ν–ˆμ„λ•Œ 주어진 μˆœμ—΄μ˜ λ°”λ‘œ 이전 μˆœμ„œμ˜ μˆœμ—΄μ„ λœ»ν•œλ‹€.

예λ₯Ό λ“€μ–΄ 12341234λŠ” N이 4인 경우 μ‚¬μ „μˆœμ—μ„œ 첫 번째의 μˆœμ—΄ μ΄λ―€λ‘œ 이전 μˆœμ—΄μ΄ μ—†κΈ° λ•Œλ¬Έμ— -1을 λ°˜ν™˜ν•˜λ©°, 12431243의 이전 μˆœμ—΄μ€ 12341234이닀.

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;
}