[C++] 백준 2697번:다음수 구하기

문제링크

2697번: 다음수 구하기

문제

어떤 수 A가 주어졌을 때, A의 다음수를 구하는 프로그램을 작성하시오.

A의 다음수는 A와 구성이 같으면서, A보다 큰 수 중에서 가장 작은 수 이다.

A와 B의 구성이 같다는 말은 A를 이루고 있는 각 자리수의 등장 횟수가, B를 이루는 각 자리수의 등장 횟수와 같을 때 이다.

예를 들어 123과 321은 구성이 같다. 왜냐하면 두 수 모두 1이 1번, 2가 1번, 3이 1번 나오기 때문이다. 마찬가지로 14232와 12243도 구성이 같다.

하지만, 14232와 14432는 구성이 같지 않다.

입력

첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 둘째 줄부터 T개 줄에는 각 테스트 케이스가 주어진다. 테스트 케이스는 한 줄로 이루어져 있으며, 수 A이다. A는 최대 80자리 자연수이다.

출력

각 테스트 케이스에 대해서, 한 줄에 하나씩 A의 다음수를 출력한다. 만약, A의 다음수가 없을 때는 BIGGEST를 출력한다.

 

풀이

문자열을 뒤에서부터 2자리씩 탐색하면서 수가 감소하는 index를 찾는다.

해당 index보다 뒤에 있으면서 index에 위치한 수보다 큰 가장 작은 원소를 찾고 자리를 바꿔준다.

index뒤의 수를 오름차순으로 정렬시킨다.

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int t;
string a;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t;
    
    while (t--) {
        cin >> a;
 
        int arr[82] = { 0 };
 
        int size = a.size();
 
        int index = 0;    // decreasing index
        string str = "";
 
        for (int i = 0; i < size; i++) {
            arr[i] = a[i] - '0';
        }
 
        int cnt = size;
 
        // find decreasing index
        for (int i = size - 1; i >= 1; i--) {
            if (arr[i] > arr[i - 1]) {
                index = i;
                break;
            }
        }
 
 
        // BIGGEST
        if (index == 0) {
            cout << "BIGGEST" << '\n';
        }
        else {
            int minNum = 9;
            int changeIndex = 0;
 
            // find minimun number under a[index]
            for (int i = index; i < size; i++) {
                if (arr[index - 1] < arr[i]) {
                    if (minNum >= arr[i]) {
                        minNum = arr[i];
                        changeIndex = i;
                    }
                }
            }
 
            //change
            arr[81] = arr[index - 1];
            arr[index - 1] = arr[changeIndex];
            arr[changeIndex] = arr[81];
 
            //sort
            sort(arr + index, arr + size);
 
            // output
            for (int i = 0; i < size; i++) {
                cout << arr[i];
            }
            cout << '\n';
        }
    }
}