[백준 python 10989] 수 정렬하기 3

[Bronze I] 수 정렬하기 3 - 10989

문제 링크

성능 요약

메모리: 31120 KB, 시간: 9604 ms

분류

정렬

제출 일자

2023년 12월 11일 20:53:23

문제 설명

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

입력

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

출력

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

  

    
    
    
    
  
import sys
input = sys.stdin.readline

n = int(input())
count = [0] * 10001
sorted_li = list()
for _ in range(n):
    i = int(input())
    count[i] += 1
for i in range(10001):
    for _ in range(count[i]):
        print(i)

풀이

그냥 정렬하는 문제인 줄 알고 정렬만 해고 제출했는데 시간초과가 나온다..

문제에서 카운팅 정렬이라는 것을 언급되어 있길래 검색해보니 카운팅 정렬(계수 정렬)은 데이터끼리 크기를 직접 비교하지 않고, 각 데이터의 개수를 센(counting) 새로운 배열을 활용해 순서를 결정하는 알고리즘이라고 한다.

  

    
    
    
    
  
data = [0, 4, 1, 3, 1, 2, 4, 1]
counts = [0]*(max(data)+1)
result = []

for num in data:
    counts[num] += 1

print(counts)

for i in range(len(counts)):
    for _ in range(counts[i]):	#counts배열의 값만큼 반복출력하기
        result.append(i)	#값을 의미하는 인덱스를 배열에 넣어주기

print(result)	#[0, 1, 1, 1, 2, 3, 4, 4]

해당 블로그에 정리가 잘 되어 있다. 가장 큰 리스트 값의 1 더한 크기로 카운팅 리스트를 만들어 준다.

각 데이터의 개수를 카운팅 리스트에 저장한다. 카운팅 리스트를 하나하나 횟수만큼 뽑아 출력한다.

이 방법을 사용하여 문제를 풀었지만, 그래도 시간초과가 떠서 확인해보니 리스트에 저장하여 뽑는 것 때문이었다.

그래서 그냥 카운팅 리스트에 있는 횟수만큼 값을 출력시켜주니 통과했다.