[백준] 10989 : 수 정렬하기 3 (Python/파이썬)

문제 링크

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

문제

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

시간 제한 5초 , 메모리 제한 8MB

입력

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

출력

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

예제

입력

10
5
2
3
1
4
2
3
5
1
7

출력

1
1
2
2
3
3
4
5
5
7

---

정답 및 풀이

import sys

n = int(sys.stdin.readline())
count = [0] * 10001

for _ in range(n):
    num = int(sys.stdin.readline())
    count[num] += 1

for i in range(1, 10001):
    for _ in range(count[i]):
        print(i)                         

1. import sys
   • 입력이 많기 때문에 sys.stdin.readline()으로 빠르게 처리
2. n = int(sys.stdin.readline())
   • 정렬할 정수의 개수를 입력받음
3. count = [0] * 10001
   • 입력 가능한 정수의 범위가 1~10,000이므로,
   • 해당 크기만큼 리스트를 만들어 각 인덱스가 등장 횟수를 저장
4. for _ in range(n):
   • 입력받은 숫자를 하나씩 읽어, count[num]의 값을 1씩 증가시켜 등장 횟수를 기록
5. for i in range(1, 10001):
   • 1부터 10000까지 순회하면서 각 숫자가 등장한 횟수(count[i])만큼 출력

---

새롭게 배운 내용 및 느낀점

• Counting Sort
  • 데이터의 값이 범위가 작기 때문에 “숫자별 등장 횟수” 를 세서 정렬
  • 횟수 세기 기반의 출력
  • 정수 범위가 좁고, 데이터 개수가 매우 많을 때 사용
  • ↔ 정수 범위가 넓고, 데이터 개수가 적당(sort(),sorted())