[백준] 10989 수 정렬하기 3 (파이썬 Python)

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

10989번: 수 정렬하기 3

문제 설명

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

---

풀이 과정

• 나의 풀이

① 첫번째 시도 

import sys
n = int(sys.stdin.readline())
num_lst = [0]*n

for i in range(n) :
    num = int(sys.stdin.readline())
    num_lst[i] = num

num_lst_sorted = sorted(num_lst)

for i in range(n) :
    print(num_lst_sorted[i])

  메모리 초과....!!!! 충격을 먹고 이유를 찾기 위해 애썼다.

 

② 두번째 시도

import sys
n = int(sys.stdin.readline())
num_lst = [0]*10001

for i in range(n) :
    num = int(sys.stdin.readline())
    num_lst[num] += 1

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

  사실 메모리 초과로 틀린 일은 이전까지 없었어서 구글링을 통해 왜 메모리 초과가 났으며 어떻게 해결해야하는지에 대해 파고 들어보았다.

 

○ Keypoint 1 "N의 수가 10000보다 작거나 같은 자연수이다."

  N의 값의 범위가 정해졌기에 num_lst를 설정할 때 n을 곱해주는것이 아닌 10001을 곱해주어 초기화시킨다.

 

○ Keypoint 2 "빠른 입력을 위한.." 

  빠른 입력을 위해 import sys 및 sys.stdin.readline() 사용.

 

○ Keypint 3 "sorted()함수 사용이 아닌 num_lst 요소 초기화를 통한 정렬" 

  주어진 입력값은 num_lst에 저장해두고 sorted()함수를 통해 정렬한 후 출력하는 것이 아닌...

  입력값을 num_lst의 인덱스 요소에 1씩 더해서 출력할 때 num_lst의 인덱스 요소가 0이 아니면 인덱스 값만큼 출력하도록 한다.

  물론 나중에 출력할 때 상향식으로 출력하기에 오름차순 정렬을 자연스럽게 할 수 있다....!!

 

---

후기

  메모리 초과로 인한 오답은 처음이었다. 하지만 키포인트는 sorted() 함수 사용이 아닌 초기화과정인듯하다...!!!!