[Algorithm] 백준 10989 수 정렬하기3 with Python

 

문제

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

입력

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

출력

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

예제 입력 1 

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1 

1
1
2
2
3
3
4
5
5
7

---

내가 짠 코드

 

이 문제는 난이도가 브론즈1로 분류되어 있는데 생각보다는 까다로웠던 문제다.

정렬 알고리즘을 하나 하나 구현해 보지는 않은 상태여서 문제를 보고 솔루션을 한 번에 떠올리지 못했다.

 

몇 번의 메모리 초과를 겪은 후 계수 정렬로 해결이 가능하다는 사실을 깨달았다.

 

계수 정렬이란 카운팅 정렬이라고도 불리는데 수의 범위가 작다면 굉장히 효율적으로 작동한다. 

데이터의 개수가 𝑁, 데이터(양수) 중 최댓값이 𝐾일 때 최악의 경우에도 수행 시간 𝑶(𝑵 + 𝑲)를 보장한다.

 

방법은 아주 간단하다.

1. 입력으로 들어올 범위만큼의 길이를 가지는 배열을 생성, 0으로 모든 값을 채움

2. 입력이 들어오면 그 수를 배열의 index로 취급하여, 해당 index의 값을 +1 해준다

 

import sys
input = sys.stdin.readline

#계수 정렬
n = int(input())

cnt = [0] * 10001  # 입력 숫자의 범위를 커버할 배열 생성

for _ in range(n):  # 숫자가 들어오면 해당 index의 값에 +1
  num = int(input())
  cnt[num ] += 1

for i in range(10001):
  for j in range(cnt[i]):
    print(i)

 

 

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

10989번: 수 정렬하기 3