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

접근법

1) Brute-Force

Brute-force 방식으로, 백트래킹을 이용한 접근법을 생각해봤으나 N이 10,000까지 가능하므로 무조건 시간초과가 납니다.

입력 : 첫째 줄에 N(1 ≤ N ≤ 10,000)이 주어진다. 
둘째 줄에 순열이 주어진다.

2) 규칙 찾기

2-1) 배열 뒤에서부터 탐색을 수행하며, 값이 작아지는 idx를 찾는다.

2-2) idx가 n과 동일하면, 해당 배열은 순열의 마지막이므로 -1을 출력하고 프로그램을 중료한다.

2-3) 배열의 뒤에서부터 반복문을 수행하며 arr[idx-1] 보다 큰 값을 발견하면 Swap을 수행한 뒤, idx를 기준으로 배열을 다시 정렬해준다.

전체 코드

//
//  main.cpp
//  10972
//
//  Created by Jun Hyeok Kim on 5/13/24.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int n;
int arr[10000];


void doSomething() {
    
    int idx=n;
    
    for (int i=n-1; i>0; i--) {
        if (arr[i] > arr[i-1]) {
            idx=i;
            break;
        }
    }
    
    if (idx == n) {
        cout << -1;
        exit(0);
    }
    
    for (int i=n-1; i>= idx; i--) {
        if (arr[i] > arr[idx-1]) {
            swap(arr[i],arr[idx-1]);
            break;
        }
    }
    
    sort(arr+idx,arr+n);
}

int main() {
    cin >> n;

    for (int i=0; i<n; i++) {
        cin >> arr[i];
    }
    
    
    doSomething();
    for (int i=0; i<n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

N,M을 활용한 수열 백트래킹에 익숙해진 나머지 규칙을 찾아내기가 조금 까다로웠다..!