[BOJ] 2697_다음수 구하기

다음수 구하기

링크: https://www.acmicpc.net/problem/2697

2697번: 다음수 구하기

 

입력받은 수의 1의 자리부터 10^k자리까지 최초로 이전 수보다 작은 수 num를 찾는다.
해당 수를 이전에 탐색했던 수 중 하나와 바꾸는데, 이는 그 중 가장 작은 값과 교환을 한다.
(다만, 찾은 수보다는 커야한다.)

그 후, 1의 자리부터 num자리까지 오름차순으로 정렬한다.
그러면 입력받은 수와 구성이 같고, 그보다는 큰 수가 새로 만들어진다.

 

• 정답 코드

    #include<iostream>
    #include<algorithm>
    using namespace std;
  
    int n;
    int findDropIdx(string &str) {
        //끝에서부터 최초 다음 수가 더 작은 인덱스를 반환
        for (size_t i = str.size() - 2; i > 0; i--)
            if (str[i] < str[i + 1])
                return i;
        return 0;
    }
    void swapStr(string &str, int idx) {
        //자기보다 큰 수 중 가장 작은 수와 swap
        pair<char, int> min;
        min.first = '9';
        min.second = idx + 1;
        for (size_t i = idx + 1; i < str.size(); i++) {
            if (min.first > str[i] && str[idx] < str[i]) {
                min.first = str[i];
                min.second = i;
            }
        }
  
        //swap
        char temp = str[idx];
        str[idx] = min.first;
        str[min.second] = temp;
    }
  
    int main() {
        cin >> n;
        while (n--) {
            string str;
            cin >> str;
  
            int idx = findDropIdx(str);
            if (idx == 0)
                cout << "BIGGEST\n";
            else {
                swapStr(str, idx);
                sort(str.begin() + idx + 1, str.end());
                cout << str << '\n';
            }
        }
        return 0;
    }