[백준/BOJ][Python] 10989번 수 정렬하기 3

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

10989번: 수 정렬하기 3

문제

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

입력

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

출력

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

예제 입력 1 복사

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1 복사

1
1
2
2
3
3
4
5
5
7

 

아이디어

정말 쉬워보이고 브론즈라서 얕봤는데 절대 얕볼 문제가 아니었다. 자꾸 메모리초과, 시간초과가 나온다....

새로 얻게 된 관점

1. 정렬할 때 빈 리스트에 입력한 숫자를 넣어서 sort 해주는 것만 생각했다.

 => list를 처음부터 많이 만들어놓고 정렬 할 수도 있다.

2. 정렬할 때 index로 할 수도 있다! 

=> 정렬하고 싶은 숫자들을 입력할 때 그 숫자 자체를 리스트에 append 하는 것이 아니라 그 숫자의 index를 1 더해주고 마지막에 출력할 때 index 안에 있는 수만큼 반복하면 된다. 

 

코드

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

check_list = [0] * 10001 # N 최댓값 10000

for i in range(N):
    input_num = int(sys.stdin.readline())
    check_list[input_num] = check_list[input_num] + 1 # index + 1
    
for i in range(10001):
    if check_list[i] != 0:
        for j in range(check_list[i]): # 리스트에 있는 수만큼 반복해서 출력
            print(i)