[Baekjoon] 10989번 : 수 정렬하기3

 

10989번: 수 정렬하기 3

 

문제 풀이

단계별로 풀어보기 - 정렬 단계엔 총 3개의 수 정렬하기 문제가 포함되어 있다.

다른 문제들은 아래와 같이 해서 제출하면 시간이나 메모리를 초과하지 않았으나

이번 문제에선 메모리 제한이 8MB로 되어있고, 입력되는 개수의 범위가 매우 커서(<=10,000,000)  메모리 초과가 발생한다.

num = int(input())
nums = []
for _ in range(num):
    nums.append(int(input()))

nums.sort()
for i in range(num):
    print(nums[i])

따라서 메모리 초과를 피하기 위해서는 수의 범위가 10,000이하로 정해져 있기 때문에 이전에 배운 계수 정렬을 이용해야 한다.

먼저 10,000까지의 리스트를 만들고 몇 개인지 체크해서 프린트 해주면 된다.

또한 입력되는 숫자의 개수가 많기 때문에 sys.stdin.readline()로 입력을 받아야 한다.

 

코드

import sys

num = int(input())
nums = [0] * 10001

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

for i in range(1, len(nums)):
    # 0개가 아니면 개수만큼 출력
    if nums[i] != 0:
        for _ in range(nums[i]):
            print(i)