[백준] 10989 수 정렬하기 3

문제

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

 

 

입력

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

출력

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

 

 

---

풀이 코드 

 

1

import sys

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

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

for idx, val in enumerate(arr):
    for j in range(val):
        if val > 0:
            print(idx)

 

enumerate 함수를 사용해 index와 value를 추출하는 방법이 있고

 

 

2

import sys

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

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

for i in range(10001):
    if arr[i] != 0:
        for j in range(arr[i]):
            print(i)

 

조건 10,000보다 작거나 같은 자연수를 이용해 출력하는 방법이 있습니다.

 

 

 

코드 설명

 

계수 정렬 알고리즘

• Counting Sort 
• 배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방법

 

데이터가 등장한 횟수를 세어 그 횟수만큼 데이터를 출력한다.

 

 

 

 

 

 

코드 풀이에 핵심은 이정도로 충분하다고 생각한다.

계수 정렬 알고리즘에 대한 자세한 설명은 알고리즘 카테고리에 추가해야겠다!

 

 

 

 

 

---

참고 글

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

10989번: 수 정렬하기 3

 

도움 글

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html