백준 10989 [계수 정렬]

이 문제는

count = int(input())

a = []

for _ in range(count):
    a.append(int(input()))

a.sort()

for i in a:
    print(i)

이렇게 그냥 파이썬 기본 내장 함수를 이용하면 메모리 초과가 발생한다.

 

따라서 (제한된 조건에서, 가장 큰 수와 가장 작은 수의 차가 크지 않다거나,, =  데이터 범위가 한정) 속도가 더 빠른 계수 정렬을 이용해서 문제를 풀어야한다.

 

import sys

count = int(input())

a = []

for _ in range(count):
    a.append(int(sys.stdin.readline()))

b = [0] * (max(a)+1)

# for i in b: # 내가 짠 간결하지 못한 코드
#     for j in a:
#         if i == j:
#             i = i + 1

for i in range(count): # 책 보고 짠 코드
    b[a[i]] = b[a[i]] + 1

for i in range(count+1): # count+1인거 주의!! (배열 b는 0부터 최댓값 범위를 모두 포함, 길이가 count+1)
    for j in range(b[i]):
        print(i)

 

이코테 책에서 배운대로 계수 정렬 이용해서 풀어보려고 했는데 메모리 초과가 그래도 발생함

그래서 input으로 받아오던거 sys.stdin.realine()으로 바꿔보고

중첩 for문으로 하던거 책 코드대로 바꿔보고 했는데 메모리 초과 발생

 

좀 더 구글링해보니까 반복문에서 append를 사용해서 리스트에 요소를 넣는 게 메모리 재할당으로 인해 메모리를 많이 잡아먹는다는 이야기를 봤음

 

그래서 append 부분을 수정해보았다..

 

import sys

count = int(input())

a = []
b = [0] * 10001

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


# for i in b:
#     for j in a:
#         if i == j:
#             i = i + 1

# for i in range(count):
#     b[a[i]] = b[a[i]] + 1

for i in range(10001):
    for j in range(b[i]):
        print(i)

append를 하지 않고 코드를 작성하기 위해서는 배여 b를 최대값일 경우 10000일 경우로 생각하고 10001 크기로 만들어준다음 입력받음과 동시에 인덱스를 증가시켜주었다.

 

ㅠㅠ