[Python/백준] 10989 수정렬3 - 메모리초과.. dict를 활용.

문제 : www.acmicpc.net/problem/10989

 

 

 

아무 생각없이 리스트를 활용하여 정렬하는 방식으로 풀면 아래와 같다.

 

import sys

n = int(sys.stdin.readline())
num_list = []

for _ in range(n):
    num_list.append(int(sys.stdin.readline()))

sorted_list = sorted(num_list)

for i in sorted_list:
    print(i)

 

이러면 메모리초과 오류가 발생한다.

 

리스트가 길어지면, append에서 메모리를 많이 사용하기 때문.

 

다른 블로그 글에서는 계수정렬을 하거나, 리스트를 미리 만들어놓고 값을 추가하는 방식으로 문제를 풀었다.

 

그런데 이런 방식은 별로 pythonic 하지 않다고 생각했고, 나는 계수정렬이 뭔지도 모르고 별로 알 생각도 없다.

 

(python sorted()가 알아서 효율적으로 해주는데, 굳이 내가 구현해야할 필요가 뭐가 있겠는가?)

 

 

그래서 그냥 dictionary를 만들어서 key를 기준으로 정렬하도록 하는 방식으로 문제를 풀었다.

 

import sys

N = int(sys.stdin.readline())
dic = {}
for i in range(N):
    num = int(sys.stdin.readline())
    if num in dic.keys(): #key가 있으면 +1, 없으면 key,val을 생성
        dic[num] += 1
    else:
        dic[num] = 1
dic = sorted(dic.items()) #key기준으로 정렬됨
for key, val in dic:
    for i in range(val):
        print(key)

 

매우 간단하게 해결할 수 있었다.