[BOJ/C++]10989번_수정렬하기3

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

 

##문제 풀기 전 내가 알고 있었어야 할 개념:

1_ 메모리 초과 문제 :

=> 1차 시도의 메모리 초과 이유 : <algorithm> 헤더파일 + qsort 연산에서 공간 메모리 초과 사용

2_ Time Limit => 시간 복잡도 :

•  2_1) 보통의 과정 (버블정렬, 퀵정렬...) 에서 O(n^2)의 이상의 시간 복잡도가 나온다. 
• 2_ 2) <iostream>에서 사용되는 cin, cout, endl 등등의 표준 stream 동기화 시간

=> (2_2)의 해결방법 : [코드]에 있는 init()함수 선언, 호출 

void init() {
 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

3_ 문제 원리(기억해놓자 언젠가 쓰일 지도...) => (2_1) 해결방법 :

 

 

#include <iostream>
//#include <algorithm>
#define SIZE 10001
 
using namespace std;
 
void init() {
 
    /*
     위 코드는 C와 C++의 표준 stream의 동기화를 끊는 역할을 한다.
      따라서 CIN과 COUT의 속도가 높아진다.
    */
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}
/*
int compare(const void* a, const void* b) {//메모리 초과(공간복잡도)
    return (*(int*)a - *(int*)b);
}
*/
 
int main() {
 
    init();
 
    int N;
    int cnt[SIZE] = {0};
 
    cin >> N;
 
 
    for (int i = 0; i < N; i++) {
        int input;
        cin >> input;
        cnt[input]++;
    }
    //qsort(arr, N, sizeof(int), compare);
 
    for (int i = 0; i < SIZE; i++) {
        if (cnt[i] != 0) {
            for (int j = 0; j < cnt[i]; j++) {
                cout << i<<'\n';
            }
        }
    }
 
 
    return 0;
}