[백준 / 1427] (C++) 소트인사이드

문제

배열을 정렬하는 것은 쉽다. 수가 주어지면, 그 수의 각 자리수를 내림차순으로 정렬해보자.

 

입력

첫째 줄에 정렬하려고 하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

코드

#include <iostream>
#include <vector>
#include <cmath>
#include <stdio.h>
#include <algorithm>

using namespace std;

int N;
vector<int> nums;

int main()
{
    cin >> N;

    while(N != 0){
        nums.push_back(N%10);
        N /= 10;
    }


    sort(nums.begin(), nums.end());


    for(int i=nums.size()-1; i>=0; --i){
        cout << nums[i];
    }

}

 

이번 문제는 별거 없어 보이지만 나는 N의 최대 수가 1억이라는 것에 집중했다. 

전에도 언급했듯이 나는 알고리즘의 최대 시간 제한을 계산할 때 주먹구구 법칙(시간복잡도가 1억을 넘으면 안됨)을 활용하여 시간 초과 유무를 판별했다. 

그러나 이번 문제의 경우에 정렬 알고리즘을 쓰면 최대한 최적의 경우더라도 1초에 1억을 넘게 된다. 

그래서 구글링을 해봤더니 옛날 기준에는 1억이라고 하지만 요즘은 컴파일러나 언어들이 좋아져서 최대 10억까지 가능하다고 한다....

아래 포스팅을 참고했다.

https://www.secmem.org/blog/2021/01/22/time-complexity/