백준 #10989, 수 정렬하기3 <Python>

 

 

 

---

문제

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

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

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

 

---

 

 

풀이

부끄럽지만, 정말 애먹었던 문제였다.

이 문제 자체의 난이도보단 사실

이런 제한 조건이 참 어렵게 했다.

​

대부분 시간, 메모리가 제한되는 경우의 코드는

미리 배열 or 리스트를 생성해놓고

for 문 한 번에 index를 증가시키는 것을 이용해서 해당 값을 한 번에 업데이트 해줘야지

시간 제한에 걸리지 않고 끝나는 것 같다.

​

이번에 이 문제 풀면서 알게 된 사실

​

1) python3보다 pypy3가 더 속도가 빠르다. 하지만 속도가 빠른 만큼 메모리를 많이 먹는다.

2) input()은 속도가 느리다. sys.stdin.readline()이 훨씬 빠르다.

​

​

코드는

0을 10001개 가진 list를 만들고

 

0~10000까지 반복문을 돌면서 

만약 1을 입력받으면 list[1] 을 0에서 1로

1을 한번 더 입력받으면 list[1]을 1에서 2로

​

5를 입력받으면 list[5]를 0에서 1로 

이런식으로 업데이트를 쭉 해준다.

​

그리고 list를 한 번씩 출력해주는 식으로 진행한다.

이 때 해당 리스트의 요소에는 해당 값이 몇 번 반복되었는지 값이 들어가있기 때문에

list[1]이 2면 1을 2번 출력해줘야 한다.

 

---

 

코드

import sys
count = int(sys.stdin.readline())

list = [0]*10001
for i in range(count):
    num = int(sys.stdin.readline())
    list[num] = list[num]+1

for i in range(10001):
    if list[i] != 0:
        for j in range(0, list[i]):
            print(i)

 

---