백준 1427번 C++

백준 1427번 소트인사이드
https://www.acmicpc.net/problem/1427

1427번: 소트인사이드

정답 코드

#include<iostream>
using namespace std;
int arr[10];
int n = 10;
int num;
int main() {
	cin >> num;
	int dx = 0;
	while (num != 0) {
		arr[dx] = num % 10;
		num = num / 10;
		dx += 1;
	}
				for (int x = 1; x < dx; x++) {
			int c = x;
			do {
				int root = (c - 1) / 2;
				if (arr[root] < arr[c]) {
					int temp = arr[root];
					arr[root] = arr[c];
					arr[c] = temp;
				}
				c = root;
			} while (c != 0);
		}
		for (int x = dx - 1; x >= 0; x--) {
			int temp = arr[0];
			arr[0] = arr[x];
			arr[x] = temp;
			int root = 0;
			int c = 1;
			do {
				c = 2 * root + 1;
				if (arr[c] < arr[c + 1] && c < x - 1)
					c++;
				if (arr[root] < arr[c] && c < x) {
					int temp = arr[root];
					arr[root] = arr[c];
					arr[c] = temp;
				}
				root = c;
			} while (c < x);
		}
		for (int x = dx - 1; x >= 0; x--)
			cout << arr[x];
}

문제 해설
배열을 정렬하는 문제입니다. 먼저 입력받은 수를 계속 나누어서 한 자리씩 배열에 집어넣습니다. 그리고 나서
힙 정렬을 이용해서 풀었습니다. 처음에는 퀵 정렬을 이용해서 풀려고 했지만 시간 제한이 2초여서 제외시켰습니다. 퀵 정렬의 경우에는 최악의 경우 시간복잡도가 O(N^2)이고 이를 계산할 경우 10억의 제곱이 됩니다.컴퓨터는 초당1억번의 계산을 할 수 있기 때문에 시간초과가 발생합니다. 그래서 시간복잡도가 더 작은 O(Nlogn)인 힙 정렬을 이용해서 풀었습니다. 그리고 10억개의 배열을 생성하면 메모리 초과가 발생하므로 10칸의 배열만 만든 후 각 자리수에 해당하는 인덱스값을 계속해서 플러스해주었습니다.