[10989] 수 정렬하기 3

10989번: 수 정렬하기 3

n개의 수를 정렬해서 차례대로 출력하는 문제이다.

요구사항들은 다음과 같다.

• 시간 제한이 5초이다.
  • 길다.
• 메모리 사용량이 8MB이다.
  • 적다.
• n개의 각 수의 범위가 1 ~ 10000이다.
  • 수의 범위가 작으므로 특별한 sort를 사용할 수 있을 것 같다.

풀이 과정은 다음과 같다.

• 1 ~ 10000까지 수를 key로 하는 defaultdict(default 0)을 만든다.
• 수를 입력받아서 defaultdict의 해당 key의 value를 1씩 올려준다.
• 1 ~ 10000까지 defaultdict의 value만큼 수를 출력한다.

수의 범위가 적을 때는 이렇게 dict를 사용해서 특별한 sort를 사용할 수 있다. 얼핏 듣기만 했는데 실제로 문제로 풀어보니 처음에 다르게 접근했다가 생각해낼 수 있었다. 나중에 응용하는 문제도 풀어봐야 겠다.

import sys
import collections

n = int(sys.stdin.readline().strip())
numbers = collections.defaultdict(lambda : 0)
for _ in range(n):
  number = int(sys.stdin.readline().strip())
  numbers[number] += 1
for number in range(1, 10001):
  for _ in range(numbers[number]):
    print(number)

import sys
import collections

n = int(sys.stdin.readline().strip())
numbers = collections.defaultdict(lambda : 0)
for _ in range(n):
  number = int(sys.stdin.readline().strip())
  numbers[number] += 1
for number in sorted(numbers.keys()):
  for _ in range(numbers[number]):
    print(number)