[백준 10989번] 수 정렬하기 3 - sort X

 

당연하게도 sort를 사용하면 메모리를 많이 먹는다는걸 모르고 문제 풀이를 시작했기 때문에 list에 입력받아 sort를 해 출력하는 코드를 먼저 짰다. ( 짜면서 이건 너무 쉬운데?? 라는 생각은 당연히 들었고... 답도 당연히 아닐것 같긴 했다.. ) 채점 결과 역시 틀리게 되었고 구글링 결과 생각한대로 sort가 메모리를 많이 잡아먹는것이 문제였다.

 

-- 내가 짠 코드 

 

# sort 사용시 메모리가 초과된다
import sys
n = int(sys.stdin.readline())
a = [0] * 10000 # 10000보다 작은 수

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

for i in range(len(a)):
    if a[i] > 0:
        for _ in range(a[i]):
            print(i+1)

입력되는 N은 10000보다 작거나 같은 수이기 때문에 다음과 같이 10000까지를 0리스트로 만들어서 해당하는 숫자를 입력받으면 해당하는 수의 인덱스를 하나씩 증가시키고, 증가되있는 숫자만큼 빼주도록 만들게 되었다. 

( 10000개의 리스트를 만든다는 건 부끄럽지만 구글링을 하다가 봐버려서 그대로 사용하게 되었다... sort가 진짜 문제인지 확신했어야 됐기 때문에..! )

 

정답은 맞았는데 10000까지 필요없는 리스트를 만들고 필요없이 0을 돌아가며 검사를 하는 이 방식이 과연 효율적인지는 잘 모르겠다. Java의 리스트를 만들때 입력을 받지 않고 미리 0리스트를 만드는 그런 느낌을 받았다.