[python] 백준 10989번 : 수 정렬하기 3

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

해당 문제는 메모리 초과가 많이 발생한 문제이다.

아래는 메모리 초과가 발생한 코드이다.

import sys
input = sys.stdin.readline

n = int(input())
arr = []
for i in range(n):
  arr.append(int(input()))
arr.sort()

for i in arr:
  print(i)

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어지므로 리스트가 너무 길게 생성되어 메모리 초과가 일어난다. 하지만 수의 범위는 10,000 이므로 중복되는 숫자가 많다. 따라서 dict 를 이용하여 1~10,000 개에 해당하는 길이의 딕셔너리만 생성하면 메모리 초과가 발생하지 않는다.

import sys
input = sys.stdin.readline
n = int(input())
ndic = dict()

for i in range(n):
    temp = int(input())
    if temp in ndic:
        ndic[temp] += 1
    else:
        ndic[temp] = 1

for i in sorted(ndic):
    for j in range(ndic[i]):
        print(i)

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다.