백준 10989 번 문제 풀이 Python 파이썬 :수 정렬하기 3

#77. 백준 10989번 문제 풀이: 수 정렬하기 3

N개의 수를 오름차순으로 정렬하는 프로그램 작성 *단, 메모리 제한 8MB. 입력: 첫 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000), 둘째 줄부터 N개의 수가 한 줄에 하나씩 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. 출력: 첫 줄부터 N개의 줄에 오름차순으로 숫자를 출력

입력/출력

--입력--
10
5
2
3
1
4
2
3
5
1
7
--출력--
1
1
2
2
3
3
4
5
5
7

문제풀이+해설

이 문제의 요지는 메모리 제한이 존재한다.
수의 최대개수가 천만개로 메모리 제한보다 많다.
즉, 메모리 제한으로 배열이나 리스트에 저장하는 게 불가능 하다.

이 문제의 해결 요지는 수의 범위가 10,000 이하의 자연수라는 것이다.
즉, 10,000개의 배열을 선언해서 배열의 인덱스값을 숫자로 간주하고, 각 배열에 카운트값 만큼이 숫자라고 간주하면 된다.
예를 들어, 숫자 최대 범위가 5까지만 있다고 가정하고 아래와 같이 되어 있다면,
   ① ② ③ ④ ⑤  : 인덱스값(인덱스를 숫자라 간주)
[0,1,2,0,0,1] : 값이 존재하는 카운트 배열
①인덱스 1개, ②인덱스 2개, ③,④인덱스 0개, ⑤인덱스 1개,
숫자로 간주하면 1,2,2,5 가 된다.

이 알고리즘은 숫자의 범위가 크지않게 한정 되어 있을 경우 사용하면 매우 효과적이다.

code sol.

코드편집/실행

import sys
# 입력시 속도를 위해 input 대신에 readline 사용.
N = int(sys.stdin.readline()) 
# 수의 개수 입력 받아 정수로 변환해 대입
ns = [0]*10001 # 0값으로 초기화된 숫자범위 크기의 리스트 선언
for _ in range(N): # 개수만큼 루프
  ns[int(sys.stdin.readline())] += 1
  # 숫자에 해당하는 인덱스의 값을 증가시킴
for i in range(10001): # 숫자의 범위내에서 루프
  if ns[i] !=0: # 배열값이 0보다 크면..숫자가 있는 것으로 간주
    for j in range(ns[i]): # 숫자가 있는 카운트 만큼
      print(i) # 한줄에 하나씩 출력