[백준][Python] 10989번: 수 정렬하기 3

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

 

>>

수 정렬하기 1, 2에서 사용한 다른 값들과 비교하는 비교정렬과는 다르게

메모리 제한이 8MB으로 배열을 사용하는 계수정렬(counting)을 사용해야한다.

 

계수정렬: 비교가 한번도 이루어지지 않고 정렬하는 알고리즘, 주어진 입력값들의 크기를 기준으로 수를 배열에 저장하여 정렬, 여기서 리스트의 인덱스를 이용 O(N) or O(N+k) 의 시간복잡도, 가장 큰 수의 영향을 받음, k가 N보다 크다면 k의 영향이 더 커서 다른 알고리즘보다 시간 복잡도가 더 커질 가능성 있음

 

import sys

n = int(sys.stdin.readline())
a = [0] * 10001

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

for i in range(1, 10001):
  if a[i] > 0:
    for _ in range(a[i]):
      print(i)

 

N개의 줄의 숫자들은 10,000보다 작거나 같은 자연수이다.

리스트의 인덱스 값을 이용하여 각 인덱스 값에 입력값들의 크기를 저장하여 반복문 사용한다.

10,001을 사용한 이유는 리스트의 인덱스는 실제 받는 입력값보다 1씩 작아 10,000일 경우를 대비하여 10,001 이다.

N개의 줄의 입력 값들을 각각 리스트의 인덱스와 입력 값이 맞는지 확인하여 1씩 더해준다.

 

10,001의 리스트 하나로 추가적인 메모리를 사용하지 않아도됨

 

 

 

python3 으로하면 성공, pypy3 으로하면 메모리초과

왜 같은 코드인데 메모리초과뜨지 >> pypy는 python보다 시간은 빠르지만 메모리를 더 많이 잡아먹는단다.

 

sys.stdout.write( ) 사용하면 통과됨

for i in range(1, 10001):
  if a[i] > 0:
    for _ in range(a[i]):
      sys.stdout.write('{}\n'.format(i))

 

 

https://www.acmicpc.net/blog/view/57

출력 속도 비교

https://stackoverflow.com/questions/45117672/pypy-large-memory-usage-compared-to-cpython

PyPy large memory usage compared to CPython