[백준] 10989번: 수 정렬하기 3

Kim Yuhyeon·2022년 3월 24일

C 백준 알고리즘

알고리즘 + 자료구조

목록 보기

26/161

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

문제

알고리즘 접근 방법

STL sort 쓰려고 했는데 메모리 초과가 나왔다..

이렇게 풀면 안되는 문제..
그리고 수의 개수 N은 최대 10,000,000개라서 입력값을 전부 저장하면 당연히 메모리 초과가 난다.

이 수는 10,000보다 작거나 같은 자연수를 입력받기 때문에,
10001 크기의 배열을 미리 만들고,
입력을 받을 때마다 해당 인덱스의 카운트를 올려주는 방식을 사용하였다.

이렇게만 하면 시간 초과다.

C++은 아래 코드를 추가하기만 해도 엄청난 속도 향상이 있다고 한다.

ios_base::sync_with_stdio(false); 
cin.tie(NULL); 
cout.tie(NULL);
위 코드는 C와 C++의 표준 stream의 동기화를 끊는 역할을 한다.
따라서 CIN과 COUT의 속도가 높아진다.

풀이

#include <iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
    cout.tie(NULL); 

    int N;
    cin >> N;

    int arr[10001] = {0,};

    for (int i=0; i<N; i++){
        int temp;
        cin >> temp; // 받은 순자가 idx
        arr[temp] += 1;
    }

    // sort(arr, arr+N); -> 메모리 초과

    for (int i=0; i<10001; i++){
        for (int j=0; j<arr[i]; j++)
            cout << i << '\n';
    }


}