[python] 백준 10989 :: 수 정렬하기 3 (도수 정렬, 계수 정렬)

[수 정렬하기 3]

🚨 메모리 제한이 8M이다.

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

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

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

풀이

전체 코드

import sys
N = int(input())

# 인덱스에 해당하는 숫자의 개수를 값으로 담을 배열
count = [0] * 10001

# count의 배열에서 정렬할 숫자의 인덱스에 해당하는 값을 1씩 증가한다.
for _ in range(N):
    count[int(sys.stdin.readline())] += 1

# count 배열을 돌면서, 값만큼 index를 출력한다.
for i in range(10001):
    for _ in range(count[i]):
        print(i)

메모리 제한이 8M로 아주 작기 때문에
최대한 메모리를 사용하지 않는 방법으로 풀어야 한다.

정렬해야 하는 숫자가 10,000보다 작거나 같다고 정해져 있으므로,
도수 정렬(계수 정렬)을 활용할 수 있다.

도수 정렬 = 계수 정렬

• 배열을 활용하는 정렬이다.
• 배열을 하나 만들어서 정렬해야 하는 숫자에 해당하는 인덱스의 값으로
  그 숫자가 등장한 횟수를 저장한다.

 

1. 정렬을 위한 배열을 만든다.

# 인덱스에 해당하는 숫자의 개수를 값으로 담을 배열
count = [0] * 10001

• 배열의 크기는 최대 숫자 + 1로 지정하면 된다.
  (index는 0부터 시작하니까 +1 해야 함!!)

 

2. 값을 입력 받으면서 count 배열에 개수를 넣는다.

# count의 배열에서 정렬할 숫자의 인덱스에 해당하는 값을 1씩 증가한다.
for _ in range(N):
    count[int(sys.stdin.readline())] += 1

• 입력 받을 수의 개수가 1 ≤ N ≤ 10,000,000라서 입력받은 값조차 배열에 저장하면 안된다.
  배열에 저장하면 메모리 초과된다 🙁 ㅠㅠ
• 값을 배열에 저장하지 말고, 입력 받자마자 정렬을 위한 배열에 정보를 저장해버려야 한다.
  여기서 정보는 이 값의 등장 횟수!!

 

3. 출력한다.

# count 배열을 돌면서, 값만큼 index를 출력한다.
for i in range(10001):
    for _ in range(count[i]):
        print(i)

• 여기서 중요한 점은, 값이 아닌 index를 출력하는 것이다!!
• 백준에서 언어를 Python3이 아닌 PyPy3으로 지정한다면 출력할 때 print(i)가 아닌
• sys.stdout.write(str(i)+"\n")*를 써야한다 🌟🔥