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

걸린 시간: 17m00s

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

접근 방법

이 문제는 메모리 제한이 8mb밖에 되지 않는다. 주어지는 N의 최대 입력은 10,000,000으로, 만약 4bytes인 int형으로 선언을 하면 약 40mb, 2bytes인 short로 하더라도 20mb가 나온다.

counting sort를 사용해야 하는데 간단하다. 최대 입력(10,000)만큼의 배열을 만들고 카운팅을 하면된다.

풀이

1#include <stdio.h> 
2int arr[10001];
3
4int main() {
5  int n; scanf("%d", &n);
6  int i,j,k;
7  for(i=0; i<n; ++i) {
8    scanf("%d", &k);
9    ++(arr[k]);
10  }
11
12  for(i=0; i<10001; ++i) {
13    for(j=0; j<arr[i]; ++j) {
14      printf("%d\n", i);
15    }
16  }
17  return 0;
18}

시간 복잡도

• 최대 입력 크기인 배열을 순회: O(N), N <= 10,000
• 각 숫자들의 출력: O(K), K = 각 숫자의 개수
• 최종 시간 복잡도: O(N・K)

공간 복잡도

• 입력 받은 N개의 입력을 저장: O(N)
• 최종 공간 복잡도: O(n)