BOJ 1427 - 소트인사이드

문제 링크

문제#

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

입력#

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

출력#

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

풀이#

숫자를 내림차순으로 출력하라는 뜻이므로 각 자리 숫자를 분리해 정렬하면 된다. 문자열로 읽어서 문자 배열을 내림차순으로 정렬하거나, 정수 배열에 넣어 정렬해도 구조는 같다.

코드는 숫자를 문자 단위로 다루면서 큰 숫자부터 다시 이어 붙여 출력한다. 자리수 자체가 많지 않아서 복잡한 기법 없이 정렬만으로 충분히 해결된다.

코드#

#include <iostream>
#include <algorithm>
using namespace std;
 
int arr[10];
 
void solve() {
 
	string s;
	cin >> s;
 
	int len = s.length();
 
	for (int i = 0; i < len; i++) 
		arr[i] = s[i] - '0';
 
	sort(arr, arr + len, greater<>());
 
	for (int j = 0; j < len; j++)
		cout << arr[j];
}
 
int main() {
    
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
    
	solve();
 
    return 0;
}

복잡도#

• 시간 복잡도: 자릿수 $D$개를 정렬하므로 $O(D \log D)$이다.
• 공간 복잡도: 자릿수를 저장하므로 $O(D)$이다.

마무리#

자리값이 아니라 자리 숫자들의 순서만 새로 정하면 되는 문제다. 각 자릿수를 분리해 내림차순으로 정렬하면 가장 큰 형태의 숫자가 바로 만들어진다.