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

문제

어려운 점

시간초과가 자꾸 났다. 오름차순 정렬을 할 때 .sort()를 이용해서 정렬했고, .append()로 입력받은 수를 배열에 넣어주었다.
그랬더니 났던 결과는 시간초과가 아닌 메모리 초과!
메모리 초과를 어떻게 해결해야 하는지 모르겠어서 다른 분들의 코드를 참고했다.

N의 범위가 N(1 ≤ N ≤ 10,000,000)였는데, 이때는 메모리초과가 발생할 수 있다.

그러나,
for문 속에서 append를 사용하게 되면 메모리 재할당이 이루어져서 메모리를 효율적으로 사용못한다. 일반적으로 입력값이 크지않은 경우에는 상관없지만 이렇게 입력값이 극한으로 많이 주어질 때에는 메모리를 좀 더 효율적으로 관리해야한다.

그래서 입력값이 10000개 까지 주어질 수 있으니 10000개 만큼의 리스트를 만들어 놓는다.

그러나 인덱스는 0부터 세기 때문에 이를 계산하기 편하게 길이가 10001인 리스트를 만든다.

풀이 순서

• 각 요소마다 [0] 할당된 리스트 생성 - 각각의 입력값을 인덱스로 하여 1씩 더하기
• 입력값 받을 때마다 그 입력값을 인덱스로 하는 원소에 1씩 더하기
• 입력 다 받고는 0보다 큰 요소들의 인덱스를 찾아서
• 그 수만큼 인덱스를 출력
  (인덱스가 해당 수임!)

풀이

from sys import stdin

n = int(stdin.readline())
arr = [0] * 10001
for i in range(n):
    arr[int(stdin.readline())] += 1

for i in range(len(arr)):
    if arr[i] > 0:
        for j in range(arr[i]):
            print(i)
    

메모리초과 풀이

퀵정렬을 이용해서 풀어도 메모리초과가 떴었다.

from sys import stdin

n = int(stdin.readline())
arr = []
for i in range(n):
    arr.append(int(stdin.readline()))

def quick_sort(arr):
    if len(arr) == 0:
        return arr
    
    pivot = arr[0]
    small_list = []
    equal_list = []
    big_list= []
    
    for i in range(arr):
        if pivot < arr[i]:
            big_list.append(arr[i])
        elif pivot > arr[i]:
            small_list.append(arr[i])
        else:
            equal_list.append(arr[i])
    
    result = quick_sort(small_list) + equal_list + quick_sort(big_list)
    
    return result

result = quick_sort(arr)    

for j in result:
    print(j)

Ref.

https://yoonsang-it.tistory.com/49