[백준 BOJ][sort] 10989 수 정렬하기 3

10989_수 정렬하기 3

링크

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

 

풀이

 

오름차순 정렬이지만 N의 범위가 10,000,000입니다. 그렇다면 배열에 담으면 메모리 초과가 나겠네요.

그래서 뒤의 조건인 ‘이 수는 10,000보다 작거나 같은 자연수이다’를 이용해서 arr[10001]을 만든 다음 입력 받은 수를 tmp라고 하면 arr[tmp]++을 해주고 출력할 때, 아래서부터 출력해주면 됩니다.

 

코드

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

#include <iostream> #include <cstdio> using namespace std;   int arr[10001];   int main() {     int n;     int i;       cin >> n;       for (i = 0; i < n; ++i) {         int tmp;         scanf("%d", &tmp);         arr[tmp]++;     }       for (i = 1; i <= 10000; ++i) {         for (int j = 0; j < arr[i]; ++j)             printf("%d\n", i);     }       return 0; } Colored by Color Scripter

cs