백준 10989번 (python) - 수 정렬하기3

수 정렬하기3

백준 > 단계별로 풀어보기 > 정렬

문제

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

입력

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

출력

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

풀이

import sys

N = int(sys.stdin.readline())

cnt = [0] * 10001

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

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

2751에서는 input()과 sys.stdin.readline() 간의 시간 초과에 관련된 문제였다면,

10989는 메모리 초과에 관련된 문제가 생겼다.

기존과 같이 sort함수를 이용해 O(NlogN)을 보장하는 형태로 작성했을 때, 메모리 초과가 발생했다.

이는 카운팅 정렬을 이용해서 해결했다.

카운팅정렬은 입력받을 자연수(또는 정수)의 범위만큼의 크기를 가진 배열을 선언하고, 입력받을때마다 해당 배열의 입력받은 정수 인덱스의 값을 1씩 증가시킨다.

예를들어, 3을 입력받았으면 다음과 같이 array[3] += 1
처럼 배열의 인덱스3 값을 1 증가시킨다.

50을 입력받았으면 다음과같이 array[50] += 1 처럼 인덱스50의 값을 1 증가시킨다.

그리고 배열을 인덱스 값이 0이 아니라면 값 만큼 반복해서 출력한다.

인덱스에 저장하면 별도의 정렬을 수행하지 않아도, 오름차순으로 정렬된다는 점을 이용한 카운팅정렬이다.