[Python] 10989 수 정렬하기 3 | 메모리 초과 | 시간 초과

~브론즈 1~

 

맨 마지막에 최종 코드가 있습니다.

제가 어떤 방식으로 헤매며 해결해 나가는지 기록합니다.

 

이 글을 읽으시는 분들도 저와 비슷한 문제에 부딪혔을 때

이 글을 통해 해결하셨으면 좋겠습니다😉

 

---

키워드

#시간복잡도 최소화  #메모리 사용 최소화 #3번의 도전

 

(틀린)

첫 번째 시도를 보시겠습니다

n = int(input())
alist = [int(input())] #리스트에 첫번째 값 대입

for i in range(n-1): #처음 입력받은 회수 차감한 만큼 반복
    a = int(input())
    count = int(len(alist)) 

    for j in range(count): #리스트에 들어있는 값 개수만큼 반복
        if a == alist[j] or a < alist[j]: #입력받은 값과 동일하거나 큰 값이나타나면 앞에 배치 
            alist.insert(j, a)
            break
        elif j == count-1: #본인보다 큰 수가 없었을 때 맨 뒤에 배치
            alist.append(a)


for i in alist:
    print(i)

해당 코드는 제한 시간과 메모리 크기가 없었으면 성공했을 것이다.

하지만 시간과 메모리 제한을 모두 초과했다는 점이 잘 못 되었다.

 

<시간 초과>

중첩 for문으로 n의 크기가 커질수록 시간은 기하급수적으로 늘어났을 것

 

 

 

(틀린)

두 번째 시도를 보시겠습니다

n = int(input())
alist = []

for i in range(n): #모든 입력을 리스트에 저장
    alist.append(input())
alist.sort() #정렬
for i in alist:
    print(i)

첫 번째 시도에 비해 확연히 코드 줄이 줄었습니다

Python의 강력한 내장함수 sort가 있잖아?! 하면서

룰루~ 이제 시간초과 해결~ 이러고 있었는데

메모리 초과가 떴다,,

 

<메모리 초과>

내장함수인 sort와 input를 이용하면 메모리 초과가 뜬다.

문제에서 제시한 최대 입력 값(10,000)을 고려하여 리스트개수를 제안한다.

또한 input을 sys.stdin.readline으로 대체하여 메모리 사용을 줄인다.

 

 

 

마지막 시도

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

for i in range(n):
    a = int(input())
    alist[a] += 1

for i in range(len(alist)):
    for j in range(alist[i]):
        print(i)

성공😎

 

 

<참고 사이트>

https://coarmok.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%ACpython-%EB%B0%B1%EC%A4%80-10989%EB%B2%88-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%B4%88%EA%B3%BC