[백준 코딩테스트(Python)] 정렬 - 수 정렬하기 3

10989번: 수 정렬하기 3

---

문제

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

 

입력

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

 

출력

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

 

---

1. 문제 접근 방식

메모리 제한이 8MB밖에 되지 않기 때문에 최대한 메모리의 사용을 적게 하는 코드를 짜는 것이 중요하다.

 

① 파이썬 sys 모듈 사용하기 (input()은 메모리를 많이 사용하기 때문에 이런 경우, sys 모듈을 활용하는 것이 좋다.)

② 카운팅 정렬 (Counting Sort) 사용

     → 비교 기반의 정렬 알고리즘은 아니며 배열을 정렬할 때 효과적이고 빠른 정렬 알고리즘이다.

https://medium.com/@manishsundriyal/counting-sort-in-javascript-abf976e66b8c

[알고리즘] 계수 정렬(Counting Sort)

 

 

2. 풀이코드

import sys

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

# counting 정렬을 하기 위해 count 리스트에 숫자의 최대 범위까지 0을 만들어줌
count = [0] * 10001

# 입력값으로 받은 수가 몇 번 들어왔는지 빈도를 저장
for _ in range(N):
    count[int(sys.stdin.readline())] += 1

# 배열의 시작부터 반복하여 저장된 빈도만큼 인덱스 값을 출력함
for i in range(10001):
    for _ in range(count[i]):
        print(i)

 

 

3. 참고 포스팅

백준 10989번 [파이썬] 수 정렬하기3