백준 10989번 수 정렬하기 (계수 정렬)

사실 나는 공간 복잡도나 시간 복잡도에 대한 기초가 없다.

그래서 다음과 같은과 같은 코드를 짜면 공간 초과 및 시간 초과의 오류가 난다. 

N = int(input())

set1 = []
for _ in range(N):
    set1.append(int(input()))

set1 = sorted(set1)

for element in set1:
    print(element)

 

그럼 공간 초과가 왜 나올까 ?

결론적으로 append를 이용하여 공간 초과가 나왔다

 

for 문 속에서 append를 사용하게 된다면 메모리 재할당이 이뤄지므로 메모리를 효율적으로 사용하지 못한다고 한다. 

관련 글은 다음 글을 참고해보자

https://wikidocs.net/21057

10_메모리 관련

 

 

그래서 append를 사용하지 않고 다음과 같이 코드를 수정해보았다.

N = int(input())

my_list = [int(input()) for _ in range(N)]
my_list = sorted(my_list)
for element in my_list:
    print(element)

그래도 메모리 초과가 나온다....

문제는 sorted 함수를 쓰면 메모리가 또 효율적으로 작동하지 않는다고 한다. 

이때 사용할 수 있는 방법 중 하나는 계수 정렬이다. 

 

문제를 보면 약 10,000,000개의 입력이 들어오지만,

입력을 받는 수의 크기가 10,000 이하라고 한다.

즉, 무조건 중복이 존재할 수 있다는 말이다. 

리스트의 인덱스 번호로 세어보자 

list의 2번 인덱스는 이제부터 >> 2가 나온 갯수이다. 

 

예를 들어 ,

list의 10 인덱스( arr[10] = 2 ) 에 2가 되어있으면 

10을 두번 출력해주면 된다. 

import sys
input = sys.stdin.readline

num = int(input())
arr = [0]*10001


for i in range(num):
    a = int(input())
    arr[a] = arr[a] + 1 

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