[백준 10989] 수 정렬하기3 / 파이썬

기본적인 방법으로 풀이하니 메모리 초과가 뜬다.

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

입력 시간을 덜 잡아먹을 수 있는 readline을 쓰고 리스트 압축 사용했다.

import sys
input = sys.stdin.readline
nums = [int(input()) for _ in range(int(input()))]
nums.sort()
for num in nums:
    print(num)

메모리 초과 뜬다.

딕셔너리로 해볼까?

import sys
input = sys.stdin.readline

nums = {}
for _ in range(int(input())):
    n = int(input())
    nums[n] = nums.get(n, 0) + 1

for k, v in nums.items():
    for _ in range(v):
        print(k)

딕셔너리는 순서가 없는것 때문에 힘들 듯 하다.

어디서 메모리가 많이 소비되는 것인지 모르겠어서 제미니에게 물어봤다.

1. 파이썬에서 정수객체는 다른 언어들과 다르게 4~8byte가 아니라 객체정보(참조횟수, 타입정보...)를 포함하기에 최소 28byte 정도 차지한다.
2. 리스트는 정수 객체들의 주소를 담는 포인터 배열을 가지는데, 포인터 하나당 8byte가 추가로 사용된다.
3. sort()는 정렬 과정에서 일시적으로 추가 메모리를 사용한다.

-> 계수정렬을 사용하면 해결할 수 있다.

❓계수 정렬 Counting Sort

• 데이터의 값을 직접 비교하는 것이 아니라, 각 숫자가 몇번 등장했는지 개수를 세어 정렬하는 알고리즘
• 데이터 최댓값 + 1 만큼(아니면 인덱스에서 1 빼던가)의 0으로 초기화한 리스트를 만들고, 데이터를 읽으며 해당 숫자를 인덱스로 하는 칸의 값을 1씩 증가
  
  ex) cnt = [0, ..., 0]
  4 발견 >> count[3]을 1로
  2 발견 >> count[1]을 1로
  4 발견 >> count [3]을 2로

import sys
input = sys.stdin.readline

cnt = [0] * 10001 # 0으로 초기화 된 리스트 생성 

for _ in range(int(input())):
    cnt[int(input())] += 1

for i in range(10001):
    if cnt[i] != 0:
        for _ in range(cnt[i]):
            print(i)