백준 10989 수 정렬하기 3 (파이썬)
접근방식
메모리초과를 조심해야하는 문제였다.
여러번의 시도 끝에 성공했다😶
- 카운팅 정렬을 사용하되 더욱 간소화된 카운팅 정렬을 사용해야했다. 카운팅정렬에 대한 개념은 아래 글에서 확인할 수 있다. 카운팅정렬 및 기본 정렬 알고리즘 정리
- 기존 같았으면 정렬되지않은 배열을 받고 이 배열의 최대값을 토대로 카운팅배열을 만들었겠지만 메모리를 위해 이 과정을 생략하고 바로 조건(10,000보다 작거나 같은 자연수) 내 가장 큰 카운팅 배열를 만들고 카운팅 배열의 값(카운팅)만큼 카운팅 배열의 인덱스를 출력하는 식으로 진행되었다.
파이썬 코드
import sys
n = int(sys.stdin.readline())
# 조건 내 가장 큰 counting array를 생성한다
counting_array = [0 for _ in range(10001)]
for i in range(n):
num = int(sys.stdin.readline())
counting_array[num] += 1
# counting array의 값 만큼 인덱스를 출력한다.
for j in range(1,10001):
count = counting_array[j]
for _ in range(count):
print(j)
