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

문제

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

 

---

 

풀이

이 문제는 계수 정렬을 이용하여 시간복잡도를 해결 할 수 있습니다.

계수 정렬은 0 리스트를 범위까지 미리 선언하고 인덱스를 이용하여 해당 숫자의 갯수를 체크합니다.
(이 문제에서 조건은 10,000보다 작거나 같은 자연수라고 했네요.)

예를 들면 10개 숫자가 5, 2, 3, 1, 4, 2, 3, 5, 1, 7 이 있습니다.
11까지 0 리스트를 만들면(인덱스 0을 생각해서 범위를 +1 해서 만듭니다.)
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

5, 2, 3, 1, 4, 2, 3, 5, 1, 7 에서
각 숫자를 카운트 한 값을 0 리스트에 넣어 줍니다.
[0, 2, 2, 2, 1, 2, 0 ,1, 0, 0 ,0]
1 - 2개
2 - 2개
3 - 2개
4 - 1개
5 - 2개
7 - 1개

오름차순으로 정렬해서 출력하라고 한다면
리스트를 하나씩 확인하고 카운트 된 갯수만큼 인덱스 값을 하나씩 출력

코드를 순서대로 작성한다면
1. 입력된 숫자를 카운트할 '0'리스트를 주어진 범위만큼 생성
2. 숫자를 하나씩 '0'리스트의 인덱스 값에 넣고 카운트 +1
3. 카운트 된 갯수만큼 인덱스 값을 하나씩 출력

---

작성 코드

N = int(input())

count = [0] * 10001 # 10,000보다 작거나 같은 자연수 범위를 미리 리스트로 만듬

for _ in range(N):
    count[int(input())] += 1 # 주어진 숫자를 입력하고 해당 인덱스 값에 카운트 +1
    
for i in range(10001): # 리스트를 하나씩 확인하고 숫자가 있으면 카운트 갯수만큼 인덱스 값을 하나씩 출력
    if count[i] != 0:
        for j in range(count[i]):
            print(i)