[알고리즘] 백준 10989 : 수 정렬하기 3 - B1

2023.04.12

import sys
input= sys.stdin.readline

n=int(input())
arr=[0] * (10001)

for _ in range(n):
    arr[int(input())]+=1

for i in range(10001):
    if arr[i]>0:
        for _ in range(arr[i]):
            print(i)

다른 풀이

import sys

n=int(input())
result=[0]*10001
for i in range(n):
    n=int(sys.stdin.readline())
    result[n]+=1

for i in range(len(result)):
    for j in range(result[i]):
        sys.stdout.write(str(i)+"\n")

check point

• 계수 정렬
  특정 조건이 부합할 때만 사용할 수 있지만 매우 빠른 알고리즘

• 일반적으로 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는다는 특징이 있음
  모든 범위를 포함하는 리스트를 선언 후, 각 데이터에 해당하는 인덱스의 값 증가.

• append와 sort로 풀었을 때 메모리초과
  메모리 제한 : 8MB,
  N의 입력값 : (1 ≤ N ≤ 10,000,000) 10,000보다 작거나 같은 자연수 -> 중복가능
  : 계수정렬 이용