백준 10989번 - 수 정렬하기 3 [python]

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

안녕하세요,  오늘은 백준 10989번 '수 정렬하기 3' 문제에 대한 Python 풀이를 공유하려 합니다. 

 

문제 이해

해당 문제는 주어진 수열을 오름차순으로 정렬하는 문제입니다. 이 문제에서 가장 중요한 점은 입력 수의 개수가 최대 10,000,000개라는 것입니다. 이렇게 많은 수의 데이터를 처리하려면 효율적인 메모리 사용과 알고리즘이 필요합니다.

 

문제 접근 방식

처음에는 일반적인 정렬 문제처럼 입력 받은 수를 리스트에 저장하고, 이를 sort() 함수를 이용해 정렬하려 했습니다.

import sys

def input():
    return sys.stdin.readline()

n = int(input())

res = []
for _ in range(n):
    a = int(input())
    res.append(a)

res.sort()

for i in res:
    print(i)

하지만 이 방식을 사용하면 '메모리 초과' 에러가 발생합니다. 왜냐하면 입력 수의 개수가 매우 크기 때문에 이를 모두 리스트에 저장하면 메모리를 과도하게 사용하게 되기 때문입니다.

 

주어진 수의 범위가 1 ~ 10,000이고, 수의 개수가 최대 10,000,000개까지 주어지는 것으로 보아 대부분의 정렬 알고리즘으로 풀기에는 시간 복잡도가 너무 크게 나옵니다.

버블 정렬, 선택 정렬, 삽입 정렬 같은 O(n^2)의 시간 복잡도를 가지는 알고리즘으로는 풀기에는 데이터의 양이 너무 많기 때문에 시간 초과가 발생합니다.

퀵 정렬, 병합 정렬, 힙 정렬 같은 O(nlogn)의 시간 복잡도를 가지는 알고리즘으로도 이 문제를 풀기에는 데이터의 양이 너무 많아 메모리 초과나 시간 초과가 발생할 확률이 큽니다.

이 문제의 경우에는 수의 범위가 제한적이고, 주어진 수가 많이 반복되는 특징 때문에 계수 정렬과 같이 O(n)의 시간 복잡도를 가지는 알고리즘을 사용하는 것이 가장 효율적입니다.

 

코드 작성

이 문제를 효율적으로 해결하기 위해서는 '계수 정렬(Counting Sort)' 알고리즘을 사용해야 합니다. 계수 정렬은 각 숫자의 개수를 세어주는 방식으로, 이 문제와 같이 숫자의 범위가 제한적이고 큰 수의 데이터를 정렬해야 할 때 매우 효율적입니다

 

import sys

def input():
    return sys.stdin.readline()

n = int(input())

count = [0] * 10001

for _ in range(n):
    num = int(input())
    count[num] += 1

for i in range(1, 10001):
    if count[i] != 0:
        for _ in range(count[i]):
            print(i)

코드 해설

입력 받는 모든 수를 리스트에 저장하는 것이 아니라, 해당 수를 인덱스로 하는 위치의 값을 1씩 증가시킵니다. 그런 다음에는 1부터 10,000까지 각 수에 대해 그 수가 몇 번 등장했는지를 출력합니다. 이때 각 수가 등장한 횟수만큼 그 수를 출력하면 되므로, 결국 입력받은 수들이 오름차순으로 출력되게 됩니다.

 

마치며

이 문제를 통해 데이터의 크기와 범위를 고려하여 적절한 알고리즘을 선택하는 것의 중요성을 배울 수 있었습니다. 특히, 메모리 제한이 있는 문제에서는 데이터의 크기와 범위에 따라 적절한 자료구조나 알고리즘을 선택해야 함을 알 수 있었습니다.

 

감사합니다.!