BAEKJOON_10989 "수 정렬하기 3" PYTHON

[백준] 10989번 Python 파이썬

 

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

10989번: 수 정렬하기 3

 

처음엔 수 정렬하기 2와 동일한 코드로 제출했는데 'Counting Sort'라는 정렬 알고리즘을 사용하여 푸는 문제였다.

아래 유튜브를 보고 계수 정렬에 대해 공부한 후 코드를 작성하였다.

 

https://www.youtube.com/watch?v=65Ui3RNibRA 

아래의 코드로 실행했더니 메모리 초과가 떴다.

import sys
n = int(sys.stdin.readline())
num = []

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

for i in range(len(num)):
    count[num[i]] += 1
    
for index in range(len(count)):
    if count[index] != 0:
        for j in range(count[index]):
            print(index)

마지막으로 n이 10,000 보다 작거나 같기 때문에 count 리스트를 [0] * 10,000 로 만들어주었다. 

import sys
n = int(sys.stdin.readline())
num = []
count = [0] * 10000 # n은 10,000보다 작거나 같다.

for _ in range(n):
    a = int(sys.stdin.readline())
    count[a-1] += 1 # 입력받은 숫자를 해당 인덱스에 넣어준다.
    
for index in range(10000):
    if count[index] != 0:
        for j in range(count[index]):
            print(index+1)

 

혼자 공부하며 올리는 블로그입니다. 틀린 내용은 댓글 남겨주시면 감사하겠습니다.