[알고리즘] 백준10989 수정렬하기3 - 파이썬

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

10989번: 수 정렬하기 3

 

 

[틀린 풀이 코드]

# 틀린 풀이
n = int(input())

a = []
for _ in range(n):
    a.append(int(input()))

a.sort()
print(*a, sep="\n")

• 이 문제는 기본 내장 함수인 sort로는 풀 수 없었다. 이유는 데이터의 개수가 최대 천만 개였고 파이썬 내장 함수의 경우 1초에 이천만 개 정도를 수행한다고 하는데 솔직히 잘 이해는 안 갔다.
  
  
• 해결방법은 계수 정렬을 활용하면 됐다.

 

[계수 정렬(Counting Sort) 알고리즘]알고리즘
- 계수 정렬은 수의 범위가 제한적일 때 사용할 수 있는 동시에 훨씬 빠른 정렬 알고리즘
- 배열의 인덱스를 특정한 데이터의 값으로 여기는 정렬 방법
- 배열의 크기는 데이터의 범위를 포함할 수 있도록 설정
- 데이터가 등장한 횟수를 센다.

 

[계수 정렬 활용한 풀이 코드]

from sys import stdin

input = stdin.readline
array = [0] * 10001

n = int(input())
for _ in range(n):
    n = int(input())
    array[n] += 1

for i in range(10001):
    if array[i] != 0:
        for _ in range(array[i]):
            print(i)

• 먼저, 만개의 데이터를 담을 수 있는 배열을 선언하고 값을 입력받을 때마다 해당 인덱스에 +1을 해준다.
  
  
• 마지막으로 배열 전체를 돌면서 0이 아닌 경우, 인덱스를 가진 수만큼 출력해주면 된다.