[Python][백준 BOJ Bronze I] 10989. 수 정렬하기 3 : 메모리 초과 해결, 계수 정렬

❌ 접근 방식 1

1. N개의 줄에 걸쳐 주어지는 수를 num이라는 리스트에 다 넣고
2. 리스트를 오름차순 정렬한 뒤
3. 리스트 요소들을 하나씩 출력했다.

import sys
n = int(sys.stdin.readline())
num = [int(sys.stdin.readline()) for _ in range(n)]

for i in sorted(num):
    print(i)

 

제출 후 만나게 된 '메모리 초과' ;;.... 어쩐지 너무 쉽다 했다 ^..^

대부분 문제들의 메모리 제한이 128MB, 256 MB인 것에 비해 이 문제는 메모리 제한이 8 MB이기 때문에 메모리 초과를 피하는 데에 초점을 두고 풀어나가야 한다.

메모리 초과 발생 이유

1. for문을 통해 입력값을 리스트(num)에 삽입한 것
2. sort(), sorted() 함수를 사용해 오름차순 정렬한 것

 

---

✅ 접근 방식 2

계수 정렬을 사용하자. 계수 정렬은 동일한 값을 가지는 데이터가 여러개 등장할 때 효과적으로 사용할 수 있다.

데이터의 크기 범위가 제한되어 있고, 정수 형태로 표현할 수 있을 때에만 사용할 수 있으며 매우 빠르게 동작한다.

계수 정렬

이것이 코딩 테스트다 with Python 강의 https://www.youtube.com/watch?v=65Ui3RNibRA&t=10s

1. 데이터 범위를 확인하고, 모든 데이터의 범위가 모두 담길 수 있도록 리스트를 생성한다. (값은 0으로 초기화)
2. 각 인덱스가 데이터의 값에 해당한다. 각각의 데이터 값이 몇 번 등장하는지 카운트한다.
3. 정렬할 데이터를 앞부터 순회하며 데이터 값에 해당하는 인덱스의 값을 1씩 증가시킨다.
   • [7] → 0+1 → 1
   • [5] → 0+1 → 1
   • [9] → 0+1 → 1
   • [0] → 0+1 → 1
   • [3] → 0+1 → 1
   • [1] → 0+1 → 1
   • [6] → 0+1 → 1
   • [2] → 0+1 → 1
   • [9] → 1+1 → 2
   • [1] → 1+1 → 2
   • ..... 정렬할 데이터 끝까지 반복!

 

 

인덱스 순서대로 출력할 수 있기 때문에 오름차순으로 정렬한 결과와 같음을 알 수 있다.

데이터 범위만큼의 인덱스를 가진 배열을 만들어야 하기 때문에 공간 복잡도가 높으나 조건만 만족한다면 퀵 정렬보다도 더 빠르게 동작한다. 데이터의 개수가 N, 데이터 중 양수 최댓값이 K일 때, 최악의 경우에도 수행 시간 O(N+K)를 보장한다.

 

---

 

문제에서 수의 개수 N의 범위가 1부터 10,000,000 이고, 주어지는 수의 범위는 10,000보다 작거나 같은 자연수이므로 중복되는 숫자들이 주어진다는 것을 알 수 있다. 

데이터의 크기 범위가 제한되어 있고, 정수 형태로 표현할 수 있으며 동일한 데이터가 여러 번 등장하므로 계수 정렬을 사용해 보자.

 

import sys
n = int(sys.stdin.readline())   # 개수 N
# 오름차순 정렬 => 계수 정렬 사용
count = [0] * 10001 # 인덱스 0 ~ 10001

for _ in range(n):
    count[int(sys.stdin.readline())] += 1

for i in range(len(count)): # 인덱스를
    for _ in range(count[i]):   # 값만큼
        print(i)    # 출력

1. 1부터 10000까지의 수가 주어지나 인덱스와 수를 동일하게 하기 위해 count = [0] * 10001 으로 초기화했다.
2. 입력값을 먼저 받은 후 리스트에 삽입하면 메모리 초과가 발생한다.
3. 따라서 입력을 받는 동시에 리스트에서 입력값과 동일한 인덱스의 값을 1씩 증가시키고
4. 값만큼 반복해서 인덱스를 출력해 준다.
5. 인덱스를 출력해야 하므로 range(len(count)) 를 사용한다.

공간 제한이 심해 공간 복잡도가 높은 계수 정렬을 사용해도 될까? 라는 의구심은 들었으나 통과한 것을 보니 10,000 정도의 범위는 괜찮은가 보다.

---

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

10989번: 수 정렬하기 3

 

요즘 나는 <정글에서 살아남기> <복붙 개발자 탈출기> 에 임하고 있다 ^,,^

실버~골드 문제도 풀어야 하는데 시간이 없어서 감이라도 잃지 않기 위해 브1 문제만 푸는 중 😭

이번 주엔 다양한 난이도와 주제를 가진 문제들을 풀어야겠다. 아자잣 ~