[파이썬python] 백준 10989번 - 메모리 초과

백준 10989번 문제를 풀어봤습니다. 

더불어 메모리제한이 작을 때, 정렬을 할 수 있는 꿀팁을 알려드리니 끝까지 봐주세요!

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

사실 이전글에서 풀어본 2751번과 문제는 거의 똑같습니다. 

2022.01.25 - [알고리즘 TIL] - [파이썬python] 백준 2751번 - merge sort

[파이썬python] 백준 2751번 - merge sort

그래서 신나게 sort함수를 써서 정답을 제출했더니...!

num = int(input())
arr = []
for i in range(num):
    arr.append(int(input()))
arr.sort()
for i in arr:
    print(i)

메모리 초과가 나오더군요.. 역시 저번과 답이 같을리가 없쥬..?

저번 문제 조건에 있던 메모리제한은 256MB였는데

이 문제는 8MB밖에 되지 않았습니다. 

 

검색을 해보니 sort()함수를 쓰면 메모리가 초과된다고 하네요. 

그렇다면 메모리를 효율적으로 사용하면서 정렬하는 방법을 지금부터 알려드리겠습니다. 

문제를 자세히 보니, 개수는 10,000,000개 까지 주어질 수 있지만, 

입력에는 10,000개보다 작거나 같은 자연수가 주어진다고 나와있습니다. 즉 중복이 될 수 있다는 소리입니다.

그럴 때 사용할 수 있는 정렬방법이 있는데요. 바로 계수정렬입니다. 

정답코드를 보면서 더 이야기 해보도록 하겠습니다. 

정답코드)

import sys
input = sys.stdin.readline
num = int(input())
arr = [0]*10000

for i in range(num):
    a = int(input())
    arr[a-1] += 1
    
for i in range(10000):
    if arr[i] != 0:
        for j in range(arr[i]):
            print(i+1)

먼저 입력으로 받을 수 있는 10,000개의 수를 담을 수 있는 배열을 만들고, 

입력받을 때 마다 그 수에 해당하는 인덱스에 +1을 해줘서 값으로 그 수의 개수를 담습니다.

그리고 다시 배열을 돌면서 값이 0이 아니라면 값만큼 인덱스에 해당하는 숫자를 출력하는 식으로 하면 

자동으로 정렬이 되는 모습을 보실 수 있습니다. 이게 바로 계수정렬의 방법입니다.

 

하지만 계수정렬만 해주면 메모리초과는 해결이 되지만, 시간초과라는 벽에 부딪히게 됩니다.

저번시간에는 pypy3를 사용해서 답변을 제출해보라고 말씀을 드렸는데, 

사실 기업에서 pypy3를 제공해주는 일은 흔치 않습니다. 

따라서 이때는 파이썬에 제공되는 sys라이브러리를 활용하는 방법을 떠올리셔야 하는데요.

sys에서 input() 대신 sys.stdin.readline()명령어를 쓰는데, 

이게 시간을 상당히 줄여줍니다. 

 

따라서 계수정렬과 sys라이브러리를 이용해서 코드를 짜면 드디어 맞았습니다!!를 보실 수 있습니다.

메모리제한이 작을 때 사용할 수 있는 정렬인 계수정렬과

시간초과가 발생할 때 사용할 수 있는 파이썬 라이브러리 sys에 대해알아보았습니다.

도움이 되셨다면 공감과 댓글 그리고 구독을 부탁드립니다.!!