[백준/Python] 10989번: 수 정렬하기 3

📖  문제 링크

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

10989번: 수 정렬하기 3

 

👩‍💻  문제풀이

 

연습문제인가? 하며 아무 생각 없이 풀었던 문제...ㅎ

메모리 초과와 런타임 에러를 반복하며 당황하여 정답률을 보니 23%라는 낮은 비율을 보이고 있었다. 

 

조건을 보니 메모리 제한이 고작 8MB였다.

 

 

 

수 정렬하기 2 (백준 2751번) 문제와 비교해 보니 현저히 작은 것을 알 수 있다.

 

 

 

이런 문제의 경우, 데이터의 입력 조건이 명확히 정해져 있고 반복되는 조건이 있다고 한다.

그래서 이전의 방식처럼 배열에 데이터를 각각 추가하는 것이 아니라,

Counting Sort 라는 방식을 사용해야 한다. 

 

 

본 문제에서는 각 숫자의 인덱스번호에 해당 숫자가 들어올 때마다 +1 카운트를 추가해주면 된다.

이때, 인덱스는 1부터 10000까지 저장되므로 배열의 크기를 10001로 만들어야 한다. (이렇게 설정하지 않으면 런타임 오류가 발생)

 

 

✅  최종 코드

import sys

n = int(input())

array = [0]*10001

for i in range(1, n+1):
    array[int(sys.stdin.readline())] += 1

for i in range(10001):
    if array[i] != 0:
        for j in range(array[i]):
            print(i)

 

 

문제에서 제시한 조건 뿐만 아니라 공간 복잡도까지 생각해야 한다는 것을 깨달았다. 

굉장히 기본적인 문제같았지만 알고리즘의 기본을 되새길 수 있는 좋은 문제인듯하다. 

다음에 다시 풀어봤을 땐 통과할 수 있길!