boj 9081 단어 맞추기

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

9081번: 단어 맞추기

문자열이지만 순열에 더 가까운 문제입니다.

주어진 단어의 사전 순으로 바로 다음 단어를 출력하는 문제로, next_permutation을 이용하였습니다.

next_permutation으로 다음 순열을 구하고, 출력하면 됩니다.

만약 마지막 단어라서 다음 순열을 구하지 못하더라도 주어진 단어를 유지하므로 그냥 출력해줍니다.

c++ 내장의 next_permutation을 사용하면 됐지만 직접 구현해보았습니다.

 

 

#include <iostream>
#include <string>
using namespace std;
 
string str;
int N;
 
bool nextPermutation() {
    int i = N - 1;
 
    while (i > 0 && str[i - 1] >= str[i]) {
        i--;
    }
 
    if (!i) return false;
 
    int j = N - 1;
    while (str[i - 1] >= str[j]) j--;
 
    swap(str[i - 1], str[j]);
 
    int k = N - 1;
    while (i < k) swap(str[i++], str[k--]);
 
    return true;
}
 
void func() {
    nextPermutation();
 
    cout << str << '\n';
}
 
void input() {
    cin >> str;
    N = str.size();
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}