백준 문제 풀이 - 수 정렬하기 3 10989번

📜 문제 이해하기

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

💡 문제 재정의

정해진 메모리안에 오름차순으로 정렬하는 문제

✏️ 계획 수립

오름차순으로 정렬하는건 간단해도 메모리가 얼마 없는게 가장 큰 문제점이다.
문제에서 주어진 10,000보다 작거나 같은 자연수인 점을 고려해서 코드를 짜면 된다.
1. 먼저 배열을 한정시켜주기위해 10001개의 배열을 만든다.
2. 같은 수가 등장할 때마다 그 배열의 값을 1 올려준다.
3. 마지막에 순서대로 출력한다.

💻 계획 수행

import sys

if __name__ == '__main__':
    cnt = int(sys.stdin.readline().rstrip())
    num_list = [0] * 10001
    for _ in range(cnt):
        num_list[int(sys.stdin.readline().rstrip())] += 1

    this_num = 0
    for num in num_list:
        for _ in range(num):
            print(this_num)
        this_num += 1

🤔 회고

한정된 메모리 안에서 오름차순으로 정렬하는 문제였다.
위 알고리즘은 시간 복잡도는 좋지 않지만 공간 복잡도가 높다는 장점이 있다.