[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)
Author And Source
이 문제에 관하여([10989] 수 정렬하기 3), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@isanghaessi/10989-수-정렬하기-3저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)