[BOJ][python] 수 정렬하기 3 - 10989

카운팅 정렬을 이용해서 푸는 문제이다

카운팅 정렬은 입력의 범위가 정해져있을때 사용할 수 있는

아주 빠른 정렬 방법으로, O(N)의 시간복잡도를 가지는 정렬방법이다.

 

n = int(input())
result=[0 for i in range(n+1)]
for i in range(n) :
    temp = int(input())
    result[temp] += 1

for idx in range(1, n+1) :
    length = result[idx]
    for n in range(result[idx]):
        print(idx)

제일 처음 카운팅 정렬을 알고 풀었던 코드이다.

정렬은 되지만 메모리 초과로 실패했다.

이 문제에서 가장 주의해야할 것은 메모리이다.

 

그래서 다른 코드를 찾아보기전에 먼저 변수 선언을 최대한 줄여보았다.

또 input을 sys.stdin으로 바꾸어보았다.

import sys
n = int(sys.stdin.readline())
# result=[0 for i in range(n)]
result = [0] * n

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

for idx in range(0, n) :
    for n in range(result[idx]):
        print(idx+1)

그래도 실패가 되었다.

 

찾아보니 카운팅을 저장할 배열 초기화를 입력 가능한 수의 최대 값에 1을 더해 10,001로 초기화를 한다.

애초에 고정된 값으로 할당하는 것이 메모리 사용에 가장 유리하다고 한다.

 

수정한 코드

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

for _ in range(n) :
    result[int(sys.stdin.readline())] += 1


for idx in range(10001) :
    # if result[idx] != 0 :
    # 찾아보면 이 줄을 꼭 다들 넣던데 
    # if문이 없어도 result[idx] 값이 0이면 for문에 들어가지 않는다.
    for n in range(result[idx]):
        print(idx)

리스트 초기화를 n으로 해준 이유는 n이 작으면 리스트의 크기도 작아지므로

메모리를 덜 쓸 수 있을까 했지만 아직 이유를 찾지 못했다.

 

---

C 언어의 sizeof와 같은 역할을 하는

sys.getsizeof로

입력받는 변수와 10001 / 입력받은 변수로 초기화한 리스트와 10001로 초기화한 리스트의

크기를 비교했지만 동일했다.

---

궁금증 해결!

백준에 질문을해서 이유를 찾아냈다.

내가 입력하는 수의 개수와 범위를 구분하지 못해서 생긴 문제였다!