문제

풀이

이 문제는 sort()함수를 사용해서 풀면 메모리 초과 문제가 발생한다.

나는 sort()를 쓰지 않고 계수 정렬 알고리즘을 이용해서 풀었다.

계수 정렬(Counting sort)

주어진 배열의 값 범위가 작은 경우 빠른 속도로 정렬하는 알고리즘

원소의 개수와 원소 최대 값이 수행시간에 영향을 준다.

예시 코드

# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언 (모든 값은 0으로 초기화)
count = [0] * (max(array) + 1)

for i in range(len(array)):
    count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가

for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

코드

import sys
input = sys.stdin.readline

n = int(input())
count = [0] * 10001

for i in range(n):
  a = int(input())
  count[a] += 1

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

결과