https://www.acmicpc.net/problem/1427

걸린 시간: 2m16s

문제

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

풀이

1#include <iostream> 
2using namespace std;
3
4int main() {
5  string s;
6  cin >> s;
7
8  const int SIZE = s.length();
9  for(int i=0; i<SIZE; ++i) {
10    bool swapped = false;
11    for(int j=0; j<SIZE-1-i; ++j) {
12      if(s[j] < s[j+1]) {
13        char temp = s[j];
14        s[j] = s[j+1];
15        s[j+1] = temp;
16        swapped = true;
17      }
18    }
19    if(!swapped) break;
20  }
21
22  cout << s << endl;
23
24  return 0;
25}

시간 복잡도

• 최종 시간 복잡도: O(S^2), S = 문자열 길이

공간 복잡도

• 최종 공간 복잡도: O(S), S = 문자열 길이