백준 10989번. 수 정렬하기 3 (Python / 파이썬)

문제

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

입력

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

출력

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

---

문제 풀이

이 문제는 단순 정렬 문제이지만 입력 받은 수를 배열에 저장하여 

sort 함수를 이용해 풀이하면 메모리 초과 문제가 발생한다. 

 

최대로 입력할 수 있는 수의 개수가 10,000,000개인데 

만약 이 수들을 모두 배열에 저장한다면 메모리 초과가 발생하고 

또한 sort함수를 이용한다해도 시간 초과 문제가 발생할 것이다. 

 

이처럼 수를 모두 배열에 저장하는 방식 말고

메모리와 시간을 효율적으로 사용하여 수를 정렬할 수 있는 방법을 생각해보았다.

n개의 수는 1부터 10,000까지의 수만 입력된다. 

따라서 10,001개의 배열을 만들고 초기값으로 0을 저장해준다. 

n개의 수가 하나씩 입력될때마다 해당 배열의 값을 1 증가시켜준다. 

이렇게 하면 배열에는 n개의 수 중 각 수의 개수가 저장된다. 

예를 들어, 5 2 3 1 4 2 3 5 1 7 의 수가 차례대로 입력된다면 배열에는 

수	1	2	3	4	5	6	7	8	9	10
수의 개수	2	2	2	1	2	0	1	0	0	0

다음과 같이 각 수가 입력된 횟수가 저장된다. 

따라서 1부터 배열에 저장된 수만큼 수를 출력하면 입력된 수들을 정렬할 수 있다. 

---

My Code

import sys 
input = sys.stdin.readline

n = int(input()) # 수의 개수 

array = [0] * 10001
for _ in range(n):
    x = int(input()) 
    array[x] += 1 # 입력된 수의 개수를 세어줌 

# 1부터 출력해주기 때문에 정렬된 결과를 얻을 수 있음 
for i in range(1, 10001):
    if array[i] != 0:
        # 입력된 횟수만큼 해당 수를 출력해줌 
        for j in range(array[i]): 
            print(i)