[Algorithm] 1일1솔 - 백준 10989 수 정렬하기 3 (python3)

문제링크

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

10989번: 수 정렬하기 3

 

문제설명

시간 제한과 메모리 제한이 있는 문제이며, 특히 메모리 제한이 빡센 문제로 단순하게 sort로 풀고 PyPy3로 돌려서 해결되는 문제가 아니다. 앞에서 블로깅했던 수 정렬하기 2(https://www.acmicpc.net/problem/2751) 문제는 메모리 제한이 256MB 였지만, 이번 문제는 메모리 제한이 8MB이므로 정렬이라는 접근보다는 새로운 접근으로 풀어야 했다.

'수 정렬하기 2' 처럼 일단 주어지는 수의 개수 N으로 빈 배열을 생성한 후, for문으로 돌며 주어지는 자연수들을 배열에 append 하는 식으로 풀이하면, 이 문제에서는 메모리 초과가 난다.

 

따라서, 주어지는 수의 개수 N의 최댓값은 10,000,000 이므로 매우 크지만, 수 자체는 10,000보다 작거나 같은 자연수이므로 계수정렬(Counting Sort) 알고리즘으로 그 크기만큼의 배열 arr을 만들고, 각 요소마다 0을 할당해주었다.

그 후, 자연수 num 이 주어질 때마다 해당 배열에서 인덱스를 매칭해서 arr[num] 에 +1을 해주며 카운팅을 해주었다.

예를 들어, 자연수 3이 주어지면 arr[3] 에 카운팅을 해주며 출력 시에는 주어진 수만큼 3을 출력하는 식이다.

 

 

문제풀이

import sys
n = int(sys.stdin.readline())

arr = [0] * 100001

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

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

 

 

---

References

https://soobarkbar.tistory.com/101

https://www.zerocho.com/category/Algorithm/post/58006da88475ed00152d6c4b

https://wikidocs.net/21057