[Python] 백준 알고리즘 #10989 수 정렬하기 3

문제풀이

 

이전에 풀었던 수 정렬하기 1,2번 문제와 동일하게 단순히 수를 입력받아 오름차순으로 정렬하는 문제이다. 

 

하지만, 이 문제는 1,2번 문제와 달리 메모리 제한이 훨씬 적다. -> 단순히 리스트에 추가시켜 sorted 함수를 이용해서 정렬할 경우, 시간 초과가 아닌 메모리 초과라는 결과가 나온다...  숫자의 개수가 1부터 10,000,000까지인 걸 보면 왜 그런지 알 수 있었다.

 

그렇게 구글링을 하던 중, 리스트의 길이를 고정시키면 메모리 초과 오류가 나오지 않는다는 방법을 찾았다. 이 방법은 직접 리스트에 숫자를 정렬시키는 것이 아니라. 숫자를 입력받을 때마다, 그 숫자에 해당하는 인덱스 위치에 값을 1씩 더해준다. 

 

 

아래 블로그 글을 참조하였다. 

Counting Sort : 계수 정렬

 

 

만약 5,4,3,2,1,3,4 을 순서대로 정렬한다고 생각하고, 등장 횟수를 전부 세어 준다.

	1	2	3	4	5
등장 횟수	1	1	2	2	1

그리고 1~5까지 를 등장횟수만큼 1,2,3,3,4,4,5 출력시키면 정렬이 된다. 

 

위와 같은 방식의 정렬은 count sort 방식으로 계수 정렬이라고 부른다. 

 

하지만 이러한 방식은 리스트의 길이만큼 무조건 순회해야 한다는 비효율적인 부분이 있지만, 이번 문제를 해결할 때 10,000,000 개의 수를 입력받아 정렬했을 경우보다는 메모리도 적게 들고, 시간적으로도 O(n)이며, O(nlogn)인 quicksort, timsort 보다 더 빠를 수 있다. 하지만 이 문제 외 대부분의 경우에는 배열에 포함된 숫자의 최댓값 만큼의 메모리를 필요로 한다고 한다. 

 

위에서 2개의 결과를 보았을 때, pypy3와 python3에서 모두 같은 코드를 작성했음에도 불구하고, pypy3에서는 메모리 초과라는 결과가 뜬다. 이유는 잘 모르겠지만, pypy3가 python3 보다 속도면에서 더 빠르지만 메모리를 더 많이 잡아먹는 것 같다. 

 

 

소스코드

 

import sys
input = sys.stdin.readline  

n = int(input())

result = [0 for i in range(10001)]

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

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

 

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3