수 정렬하기 3 - 10989

10989번: 수 정렬하기 3

이것도 역시 이전 수 정렬하기와 같은 문제지만 다른 조건이 추가됐다.

수 정렬하기 2에서 구현한 방법으로 하면 이번엔 메모리 초과 에러가 난다.

입력 값 : $N (1 ≤ N ≤ 10,000,000)$

메모리 제한 : $8MB$

시행 착오 1 🥲

가장 중요한 포인트는 메모리 제한이 8MB라는 점

입력 받는 숫자들을 배열에 전부 저장하는 방식으로 구현하면 메모리 초과 에러가 난다.

그래서 생각한 방법은 merge sort의 merge 부분만 가져와서 입력 받는 숫자를 바로 합치는 방식으로 구현해보려고 했지만 생각보다 너무 복잡하고 어려웠다.

맞았습니다! 풀이

결국 팀원분 코드를 참고했는데, 계수(Counting) 정렬을 사용하면 풀리는 문제였다.

• 숫자의 갯수를 저장해서 순차적으로 출력하는 정렬 방식

• 입력 받는 수의 범위가 제한적일 때 효율적인 알고리즘

  -> 배열의 크기는 숫자의 범위, 인덱스는 숫자의 값으로 설정

import sys
N = int(sys.stdin.readline())
count = [0] * 10001  # 숫자의 범위가 10000 이하이기 때문

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

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

(+) 추가 Tip

백준에서 파이썬 코드를 제출할 때, PyPy3와 Python3 두 가지의 버전의 언어로 지원한다.

• PyPy3 : JIT 컴파일러 사용, 자주 쓰이는 코드를 캐싱하는 기능을 포함
  • 인터프리터의 느린 실행 속도를 개선하기 위해 사용
  • 복잡한 문제에서 반복 연산을 많이 하는 경우 효율적이다!
• Python 3: 비교적 간단한 문제를 풀 때 효율적이다.
  • 대체적으로 PyPy3보다 적은 메모리를 사용한다.

맨 위로 이동하기