백준 10989: 수 정렬하기 3 (Python)

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

10989번: 수 정렬하기 3

 

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

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

for i in range(10001):
    if a[i] != 0:
        for j in range(a[i]):
            sys.stdout.write(str(i)+'\n')

 

 

이 문제는 메모리 제한이 아주 작게 걸려 있다..!! 

그래서 for문을 돌면서 리스트에 원소를 추가하면 주어진 메모리를 초과한다

 

counting sort -> 각 숫자가 몇 번 들어갔는지 셈

이 정렬을 이용해서 이 문제를 풀 수 있다

 

문제에서 숫자의 범위가 1~10000라고 했으니 미리 크기가 10000인 리스트를 만들어놓고

각 인덱스마다 몇 번 숫자가 들어갔는지 입력 받으면서 바로 카운팅한다

여기서 10001을 한 이유는 인덱스는 0부터 시작하기 때문이다...!!

튼 그렇게 카운팅해서 그 횟수만큼 1부터 반복 출력해주면 됨~~