[백준] 10989 수 정렬하기 3 (브론즈1) / 메모리초과 해결 : sort() 말고 계수정렬

문제요약

나의 코드 및 설명

• 수의 개수는 10,000,000개까지 주어질 수 있지만, 입력에는 10,000보다 작거나 같은 자연수가 주어진다고 한다. 즉, 중복이 될 수 있다. 이럴 때는 계수정렬을 활용하면 된다.
• 입력으로 받을 수 있는 10,000개의 수를 담을 수 있는 배열을 만들고, 입력받을 때마다 그 수에 해당하는 인덱스에 +1씩 해주어 그 수의 개수를 담는다.
• for문으로 통해, 10,000개의 배열 중 숫자가 담긴 인덱스만 출력한다.

import sys

n = int(input())
arr = [0] * 10001

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

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

피드백

sort() 메서드를 활용해서 문제를 풀었다가 메모리초과가 발생했다. 메모리를 효율적으로 사용하면서 정렬하는 방법인 계수정렬을 학습할 수 있었다. 같은 유형의 문제가 등장했을 때, 배열을 활용하여 문제를 해결하는 습관을 길러야겠다.