[백준] 10989 수 정렬하기 3

10989- 수 정렬하기 3

문제

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

입력

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

출력

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

이 문제는 제한 조건을 필히 확인해야 한다.

python3의 경우, 메모리 제한이 8MB이다.
-> 문제에서 입력이 N(1 ≤ N ≤ 10,000,000)인데 메모리 제한이 8,000,000Byte 라는 건 리스트에 다 저장해서 정렬하지 말라는 뜻이다.

문제 조건에서 계수 정렬을 사용해야 함을 알아야 한다.
(처음에 조건 안 읽고 병합 정렬 썻다가 안 돼서 다시 확인했다 ㅎㅎ)

#메모리 초과 -> 입력하는 모든 수를 저장하면 안 됨
import sys

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

#입력 값: 자연수(10,000보다 작음)
lis=[0]*100000 #0이 10000개 있는 리스트 생성 

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

#출력 (print 사용 여부 고려)
for i in range(len(lis)):
    for j in range(lis[i]):
        print(i)

해결 코드이다.

계수 정렬은
별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 알고리즘
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용할 수 있음.

인덱스 값이 나오면 해당 인덱스의 요소 값 +=1 해주고
출력 시에 인덱스 요소 값만큼 반복 출력해주면 해결된다!

이 문제는 내장 함수(sort, sorted)로 못 풀어서 정답 비율이 낮은 듯하다