백준 10989번 [Python] 문제풀이 (수 정렬하기 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

 

 

알고리즘 분류

ㆍ정렬

 

 

파이썬 코드(메모리초과)

import sys
n = int(input())

d = {}                                # 딕셔너리

for _ in range(n):
	x = int(sys.stdin.readline())

	if x in d: d[x] =  d[x] + 1       # x가 존재한다면 밸류 + 1
	else: d[x] = 1                    # 없다면 {x, 1} 입력

result = sorted(d.item())

for i in result:
	for _ in range(i[1]):
		print(i[0])

뭘 해도 메모리초과, 시간초과가 떠서 찾아본 방법

딕셔너리로 편리하게 만들 수 있다.

하지만 메모리 제한 기준이 바뀌었는지 메모리초과로 실패;;

 

파이썬 코드(성공)

import sys

result = [0 for i in range(10001)]
for i in range(int(input())):
	x = int(sys.stdin.readline())
    result[x] += 1

for i in range(10001):
    if result[i] > 0:
        for j in range(result[i]):
            print(i)

모든 입력값을 저장할 필요없이

입력값의 개수만 입력값에 해당하는 위치에 저장하면

천만까지 저장하더라도 result 리스트 내에서 해결 가능하다.

 

이론을 아는 것과 구현하는 것은 다른 문제임을 통감했다.