백준 문제 중 10989번, 정렬, ‘수 정렬하기 3’

백준 문제 중 10989번

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

문제

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

입력

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

출력

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

---

풀이

문제에 명시되진 않았지만 도수정렬(카운팅정렬)을 사용하라는 힌트가 있다.

• 도수정렬이란 배열 원소의 대소를 비교하지않고 원소마다 도수 분포표를 만든뒤 누적분포표와 배열의 값을 대조해가며 정렬을 하는 방법이다.자세한 설명

from typing import MutableSequence

def fsort(a:MutableSequence,max:int)->None:

    n = len(a)
    f = [0]*(max+1)
    b = [0]*n

    for i in range(n):
        f[a[i]]+=1
    for i in range(1,max+1):
        f[i]+=f[i-1]
    for i in range(n-1,-1,-1):
        f[a[i]]-=1
        b[f[a[i]]]=a[i]
    for i in range(n):
        a[i]=b[i]

n=int(input())

nums = [None]*n

for i in range(n):
    nums[i]=int(input())

fsort(nums,max(nums))

for num in nums:
    print(num)

5
5
4
3
2
1
1
2
3
4
5

도수정렬을 이용한 정렬을 성공했으나 이렇게 제출을 했더니 메모리초과 오류가 떴고 이 문제의 키포인트가 메모리임을 알게되었다.

고민 해봤지만 방법이 막막해서 검색을 통해 해결했다.

풀이의 핵심은 입력제한이 10001개의 수로 비교적 입력이 적은편이니 10001개의 리스트를 0으로 초기화 한뒤 입력값을 받고 입력값과 같은 인덱스에 있는 배열의 값을 누적으로 더한뒤 누적값만큼 배열을 순서대로 출력한다.

import sys

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

nums = [0]*10001

for _ in range(n):
    temp = int(input())
    num[temp]+=1
    
for i in range(10001):
    if num[i]!=0:
        for j in range(num[i]):
            print(i)

배운점

내가 배웠던 이론적인 카운팅정렬은 위에서 실패했던 코드에 가까운데 어느정도 생각해보면 아래 방법도 일종위 카운팅 정렬이라고 할 수 있는것 같다.