[백준] 10989 수 정렬하기 3 (Baekjoon Problem 10989: Sort 3)

문제 출처

[문제 요약]

처음에 주어질 수의 개수 N이 주어진다.

그 다음부터는 N의 개수만큼 숫자가 주어진다.

주어지는 숫자는 10000이하의 자연수이며 중복이 있다.

이를 정렬해서 한 줄에 하나의 수를 프린트하는 코드를 짜면 된다.

[풀이]

시간 제한이 있기에 최대한 빠른 알고리즘을 만들자.

input()대신 stdin.readline()으로 입력을 받자

그리고 defaultdict()를 사용하자 (hashing이라서 넣는데 O(n)이다).

 

우선 dictionary = defaultdict(int)로 하면 키가 없는 경우 그 값은 0으로 설정이 된다.

이후 N만큼 룹을 돌면서 입력을 key로, value는 1씩 더해주면 된다.

그러면 dictionary에는 10000까지 수중에 존재하는 수에는 해당 수가 몇개 존재하는지 value값이 있을거다.

 

그 다음에 룹을 1부터 10000까지 (10000+1로 줘야함) 돌면서

존재하는 key에 대해서는 해당 value값만큼 룹을 한번 더 돌면서 해당 key를 프린트 해주면 됨.

[유의할 점]

풀이에도 적었지만 10000이하라서 10000이 포함되어야 한다.

다른 시간 제한이 있던 문제에서 리스트에 넣으면서 sort하는 방법은 n^2라서 시간 초과가 뜬다.

[파이썬 3 코드]

# -*- coding: utf-8 -*-
from sys import stdin
from collections import defaultdict

if __name__ == "__main__":
    n = int(stdin.readline())

    MAX_NUM = 10000

    dictionary = defaultdict(int)
    for i in range(n):
        toadd = int(stdin.readline())
        dictionary[toadd] += 1

    for j in range(1, MAX_NUM+1):
        for k in range(dictionary[j]):
            print(j)