[BOJ/Python] 10989. 수 정렬하기 3

문제

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

 

<입력>

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

 

<출력>

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

 

<나의 코드>

# 메모리 초과
n = int(input())

array = [0] * (n + 1)
data = []
for i in range(n):
    data.append(int(input()))
    array[data[i]] += 1

for i in range(len(array)):
    for j in range(array[i]):
        print(i)

 

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

array = [0 for _ in range(10001)]
data = []
for i in range(n):
    data = int(sys.stdin.readline())
    array[data] += 1

for i in range(len(array)):
    for j in range(array[i]):
        print(i)

<REVIEW>

이 문제는 시간 제한 3초, 메모리 제한 8MB로 메모리 제한을 신경써야한다. 이코테 책에서 이러한 문제는 계수정렬로 푸는 것이 좋다고 한게 생각나 계수 정렬(Counting Sort)을 사용했다. 첫번째 코드인데 메모리 제한이 떴다..ㅜㅠ아마 메모리 제한 때문에 입력받은 정보를 append로 먼저 저장하고 정렬을 해서 그런 것 같다. 그래서 문제를 보면 주어진 수가 10,000이 넘지 않는다고 하니(앞으로 이러한 문장을 유심히 봐야겠다!!) 10,000의 배열을 사전에 선언하고 입력받은 정수값에 대응되는 인덱스 값을 1 더해주는 방식으로 작성했다. 결과는 상당히 오래 걸리긴 했지만 통과!!

 

<출처>

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