(Python) 백준 10989번 - 수 정렬하기 3

 

문제 링크 : https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

풀이

원래 브론즈 문제는 포스팅하지 않으려 했으나 문제와 관련하여 정리할 개념들이 많이 있어서 풀이를 적어보려고 한다.

 

메모리 제한과 시간 제한이 있어 단순하게 python의 sort함수로는 이 문제를 풀 수 없어서 계수정렬을 이용하여 풀었다.

count = [0] * 10001
for _ in range(int(input())):
    count[int(input())] += 1
for i in range(len(count)):
    if(count[i] != 0):
        for _ in range(count[i]):
            print(i)

처음에는 input()을 사용하여 구현하였는데 이렇게 하게 되면 시간초과가 발생한다.

 

그래서 input()보다 더 빠른 sys.stdin.readline()을 이용하여 문제를 풀었다.

import sys
count = [0] * 10001
for _ in range(int(sys.stdin.readline())):
    count[int(sys.stdin.readline())] += 1
for i in range(len(count)):
    if(count[i] != 0):
        for _ in range(count[i]):
            print(i)

 

※ 참고

1. 계수정렬(카운팅 소트)

https://lildev.tistory.com/26

계수 정렬

 

2. input() vs sys.stdin.readline()

https://lildev.tistory.com/25

(Python) input() vs sys.stdin.readline()