[C++] 백준 2992번:크면서 작은 수

문제링크

2992번: 크면서 작은 수

문제

정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다.

수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 같다. 하지만, 123과 432는 구성이 같지 않다.

입력

첫째 줄에 X가 주어진다. (1 ≤ X ≤ 999999) X는 0으로 시작하지 않는다.

출력

첫째 줄에 결과를 출력한다. 만약 그러한 숫자가 없는 경우에는 0을 출력한다.

 

풀이

1. 우측 끝부터 연속된 두 자리 수를 비교하여 작아지는 위치를 찾는다.
2. 해당 위치부터 우측에 있는 수 중 해당 수보다 크지만 크기가 가장 작은 것을 찾는다.

예를 들어 설명하면 21713인 경우 2가 찾는 위치이고, 3이 2보다 크지만 크기가 가장 작은 수가 되는 것이다.

1. 두 수의 위치를 바꾸고 찾은 위치 뒤부터 오름차순으로 정렬하여 출력한다.

 

코드

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
string x;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    cin >> x;
    int size = x.size();
    int* arr = new int[size];
 
    // make string to char array
    for (int i = 0; i < size; i++) { 
        arr[i] = x[i] - '0';
    }
 
    // find the descending index
    int index = 0;
    int num = 0;
    for (int i = size-1; i >= 1 ; i--) {
        if (arr[i - 1] < arr[i]) {
            index = i;
            num = arr[i - 1];
            break;
        }
    }
 
    // end condition
    if (index == 0) {
        cout << 0;
        return 0;
    }
 
    // find the number a little big than num for to change
    int changeNum = 9;
    int changeIndex = index;
    for (int i = index; i < size; i++) {
        if (arr[i] > num && arr[i] < changeNum) {
            changeNum = arr[i];
            changeIndex = i;
        }
    }
 
    // change 
    int tmp = arr[index - 1];
    arr[index - 1] = arr[changeIndex];
    arr[changeIndex] = tmp;
 
    // sort
    sort(arr + index, arr + size);
 
    // output
    for (int i = 0; i < size; i++) {
        cout << arr[i];
    }
 
}

 

메모

2687번 다음수 구하기와 비슷한 문제다. 아니 거의 똑같다. 몇줄만 바꿔서 제출해도 맞을정도다...