입력값과 같은 구성의 수 중 가장 작은 큰 수: NextPermutation

 

내일 풀 수학 문제의 개수는 오늘 푼 문제 개수의 수와 숫자의 구성이 같으면서, 오늘 푼 문제 개수의 수보다 큰 수 중 가장 작은 수입니다.

예를 들어, 오늘 67문제를 풀었으면 다음 날 76문제를 풉니다. 오늘 푼 문제의 개수를 줬을 때 다음날 풀 문제의 개수를 출력하는 프로그램을 작성하세요.

---

입력

오늘 푼 문제의 개수 자연수 N

1<= N <= 999999

 

출력

다음날 풀 문제의 개수 출력

---

문제요약

입력값과 같은 구성의 수 중 가장 작은 큰 수

---

풀이 포인트

• Next-permutation
• 정렬

---

REVIEW

경우의 수가 다양해지면 자꾸 생각하길 포기한다.

작은 단계로 나누어 생각하는 법을 또 명심!

999999까지가 아닌 1000까지만 해서 생각해보고 넓히고 하면 됌!

---

CODE

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;

int nextProblemCount(int todayCount) {
    string todayStr = to_string(todayCount);

    bool hasNext = next_permutation(todayStr.begin(), todayStr.end());
    
    if (hasNext) {
        return stoi(todayStr);
    }
    return -1;
}

int main() {
    int todayCount;
    
    cin >> todayCount;
    
    int nextCount = nextProblemCount(todayCount);
    
    if (nextCount != -1) {
        cout << nextCount << endl;
    } else {
        
    }
    
    return 0;
}

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

using namespace std;

int nextProblemCount(int todayCount) {
  
    string todayStr = to_string(todayCount);
    int n = todayStr.length();
    
    // 1. 뒤에서부터 감소하는 부분 찾기
    int i = n - 2;
    while (i >= 0 && todayStr[i] >= todayStr[i + 1]) {
        i--;
    }
    
    // 모든 수가 내림차순이면 다음 순열이 없으므로 -1 반환
    if (i == -1) {
        return -1;
    }
    
    // 2. 감소하는 부분의 오른쪽에서 가장 작은 숫자 찾기
    int j = n - 1;
    while (todayStr[j] <= todayStr[i]) {
        j--;
    }
    
    // 3. 숫자 교체
    swap(todayStr[i], todayStr[j]);
    
    // 4. 교체한 숫자 오른쪽 부분을 오름차순으로 정렬
    reverse(todayStr.begin() + i + 1, todayStr.end());
    
    return stoi(todayStr);
}

int main() {
    int todayCount;
    cin >> todayCount;
    
    int nextCount = nextProblemCount(todayCount);
    
    if (nextCount != -1) {
        cout << nextCount << endl;
    } else {
        cout << "No next permutation" << endl;
    }
    
    return 0;
}