[백준 2992] 크면서 작은 수 (다음 순열 찾기 & next_permutation사용법)

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

2992번: 크면서 작은 수

bool next_permutation

동작 : 사전식 순서로 다음 순열 찾는것

> 매소드 형태: 
    bool next_permutation (BidirectionalIterator first, BidirectionalIterator last);

> 시간 복잡도 : O(N!)

> 사용법 : 한번 저거 사용하면 정렬시키고 적용;

> 매개변수 : 
    first.iterator
    last.iterator

> 리턴형 :
    다음 순열이 있다면 true 리턴
    없다면 false 리턴

//prev_permutation도 있단다!.

그래서 이문제는 어떻게 해결하는건가 하면---

 

'다음 순열이 존재하는가?'이다.

 

1 2 3 4 5 6 7 8 9 10 11 12

#include <iostream> #include <string> #include <algorithm> using namespace std;   int main() {     string str; cin >> str;     if (next_permutation(str.begin(), str.end()))         cout << str << '\n';     else         cout << 0 << '\n'; } Colored by Color Scripter

cs

 

---

그런데.. 억울한 점이 있다.

위와 같은 논리로 구현했는데 틀렸다고 하니.. 어떤게 잘못된건지 반례 찾아봐야 할듯

 

위와 같은 논리로 구현했는데. 틀렸다고 했다.. 어떤게 잘못된건지 반례를 찾아봐야 할것같다

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

#include <iostream> #include <vector> #include <queue> #include <stack> #include <string> #include <algorithm> using namespace std;   int main() {     ios::sync_with_stdio(false); cin.tie(NULL);     string str; cin >> str;     string subStr = "";     for (int i = str.size() - 1; i >= 0; i--)     {         subStr = str.substr(i, str.size());         string maxSubStr = subStr; sort(maxSubStr.begin(), maxSubStr.end(), greater<char>());         if (maxSubStr != subStr)         {             int nextIdx = 1;             while (subStr[0] < subStr[nextIdx]) {                 nextIdx++;             }             int cnt = nextIdx - 1;             while (subStr[cnt] == subStr[nextIdx - 1]) {                 nextIdx--;             }             vector<char> bufStr(subStr.begin(), subStr.end());               char temp = bufStr[nextIdx];             bufStr[nextIdx] = bufStr[0];             bufStr[0] = temp;             sort(bufStr.begin() + nextIdx, bufStr.end());               for (int j = str.size() - 1; j >= i; j--) {                 str[j] = bufStr.back();                 bufStr.pop_back();             }             cout << str << '\n';             return 0;         }     }     cout << 0 << '\n';     return 0; } Colored by Color Scripter

cs