문제

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

www.acmicpc.net/problem/10989

  • 입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

  • 출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

최종 코드

앞선 2751번 수 정렬하기2(풀이) 문제에선 시간복잡도를 줄이기 위해 input 대신 readline을 사용했다면, 이번 문제에서는 공간복잡도를 고려해야 했다.

import sys

n = int(sys.stdin.readline())
arr = [0]*10001

for i in range(n):
    arr[int(sys.stdin.readline())] += 1

for i in range(1, 10001):
    if arr[i] != 0:
        for j in range(arr[i]):
            print(i)

계수정렬

공간복잡도를 고려하기 위해서 계수정렬(Count sort)을 사용하였다. 계수정렬은 데이터의 크기 범위가 제한되어 정수로 표현할 수 있을 때만 사용할 수 있다.

이 문제에서는 숫자가 1 ~ 10,000으로 제한되어 있기 때문에 크기가 10,000인 리스트를 생성하여 계수정렬을 사용할 수 있었다.

계수정렬은 해당 배열의 데이터 값과 동일한 인덱스의 데이터를 1씩 증가시키는 방법이다. 그리고 리스트의 데이터만큼 반복해서 인덱스 값을 출력해주면 배열을 정렬할 수 있다.

계수정렬의 시간복잡도

계수정렬의 경우 데이터의 개수를 N, 최대값을 K라고 할 때 시간복잡도는 O(N+K) 로 아주 빠르다.

하지만 데이터가 0과 999999만 존재할 때에도 크기가 100만인 리스트를 생성해야 해서 경우에 따라 비효율적일 수도 있다.

더불어 효율적인 메모리 관리에 대한 자세한 설명은 !여기!를 참고하자!

참고 사이트