백준-수 정렬하기

수 정렬하기 3개 문제를 풀어보았다.

문제

1. 수 정렬하기
2. 수 정렬하기 2
3. 수 정렬하기 3

풀이

1. 문제조건 해석

   세 문제 모두 단순 정렬 문제이다.

   1번 문제는 n의 개수가 1000이고, 절대값이 1000보다 작거나 같다.

   2번 문제는 n의 개수가 1,000,000이고, 절대값이 1,000,000보다 작거나 같다.

   3번 문제는 n의 개수가 10,000,000이고, 절대값이 10,000보다 작거나 같다.

2. 알고리즘

   1번 문제는 힙 정렬 알고리즘

   2번 문제도 힙 정렬 알고리즘

   3번 문제는 힙 정렬로는 메모리 초과 난다. 수가 10,000보다 작으므로 카운트 정렬 알고리즘으로 해결했다.

   파이썬 정렬 알고리즘 정리

3. 코드

   1. 1번 문제

    import heapq
    n = int(input())
    arr = []
    for _ in range(n):
        heapq.heappush(arr, int(input()))
    for _ in range(len(arr)):
        print(heapq.heappop(arr))
   

   1. 2번 문제

    import heapq
    from sys import stdin
    input = stdin.readline
    n = int(input().rstrip())
    arr = []
    for _ in range(n):
        heapq.heappush(arr, int(input().rstrip()))
    for _ in range(n):
        print(heapq.heappop(arr))
   

   1. 3번 문제

    from sys import stdin
    input = stdin.readline
    n = int(input().rstrip())
    counts = [0 for _ in range(10001)]
    for _ in range(n):
        counts[int(input().rstrip())] += 1
    idx = 1
    for i in counts[1:]:
        for j in range(i):
            print(idx)
        idx += 1