boj-10989(Counting_Sort_Variation without Original_Array)

백준 10989번을 풀면서, 힘들었던 점을 적어보려고 한다.
일단 input 갯수가 최댓값이 10,000,000이기에 단순 계산만으로도
int형 4byte * 10,000,000 = 40,000,000byte = 40MB 로
메모리 제한인 8MB를 훨씬 뛰어넘게 된다.
그래서 처음에 Counting Sort를 활용하여, 싱글벙글 작성했는데도 메모리 제한이 일어나길래 왜인지 생각해보니까
생각없이 들어오는 input number를 다 List에 저장해버려서 일어나는 문제였다.. ㅠ

그래서 Input을 저장하지않고 푸는 방법에 대해서 생각해보니까, 어차피 우리는 출력만 할거니까 들어오는 횟수도 저장했겠다.
그러면 그냥 순서만 맞춰서 출력해주면 되는거 아닌가라는 아이디어로 코드를 개선해보았다.
private gist에 막 쓴 코드이므로,,,, 주석은 막 작성했다..

import sys
input = sys.stdin.readline
MAX_NUM = 10000

num = int(input())
sorted_list = []

count = [0] * (MAX_NUM + 1)
count_sum = [0] * (MAX_NUM + 1)

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

count_sum[0] = count[0]
for i in range(1, MAX_NUM+1):
    count_sum[i] = count_sum[i-1] + count[i] # 누적합 구하기, 이전 count_sum과 그다음 숫자의 count를 더해서 누적합 갱신 

# sorted_list = [0] * (num + 1)

for i in range(MAX_NUM, 0, -1): # 맨 뒤 위치부터 반복
    if count[i] != 0:
        # sorted_list[ count_sum[ i ] ] = i # num_list 입력받은 배열의 숫자의 누적합에 해당하는 정렬된 리스트(sorted_list)index에 넣어준다.
        count_sum[i] -= 1 # 그리고 해당 숫자의 누적합을 1 감소시켜줌으로써, 다음 그 숫자가 들어가야할 index는 하나 감소된 곳에 저장 되는 것

for i in range(1, MAX_NUM + 1):
    if count[i] != 0:
        for _ in range(count[i]):
            sys.stdout.write(str(i)+'\n')

그리고 코드를 작성하고, 설명을 해보려고 쓰는 도중에 느낀건데, 누적합을 저장하고 sorted_list에 넣어주는 부분인

count_sum[0] = count[0]
for i in range(1, MAX_NUM+1):
    count_sum[i] = count_sum[i-1] + count[i] # 누적합 구하기, 이전 count_sum과 그다음 숫자의 count를 더해서 누적합 갱신 

# sorted_list = [0] * (num + 1)

for i in range(MAX_NUM, 0, -1): # 맨 뒤 위치부터 반복
    if count[i] != 0:
        # sorted_list[ count_sum[ i ] ] = i # num_list 입력받은 배열의 숫자의 누적합에 해당하는 정렬된 리스트(sorted_list)index에 넣어준다.
        count_sum[i] -= 1 # 그리고 해당 숫자의 누적합을 1 감소시켜줌으로써, 다음 그 숫자가 들어가야할 index는 하나 감소된 곳에 저장 되는 것

이부분 또한 없어져도 괜찮은 것 같다.
출력하는 방법이 그냥 count List에 입력이 들어온 숫자에 해당하는 number를 증가시켜줌으로써, 그 횟수만큼 반복하여 출력하는 것이기에 이 과정이 무의미한 과정으로 해석된다. 귀찮으므로.. 지우지 않았다..

모든 코드를 깔끔하게 정리하고 나면

import sys
input = sys.stdin.readline
MAX_NUM = 10000

num = int(input())
count = [0] * (MAX_NUM + 1)

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

for i in range(1, MAX_NUM + 1):
    if count[i] != 0:
        for _ in range(count[i]):
            sys.stdout.write(str(i)+'\n')

이렇게 정리가 된다.
어차피 들어올 숫자의 최댓값은 10000이기에 MAX_NUM 변수에 저장해두었고,
num에 들어올 input의 갯수를 받아주고, count는 MAX_NUM 의 갯수보다 1개 더 많게 생성해준다.
왜냐하면 count의 index 자리에 들어온 해당하는 숫자를 그대로 사용할 것이기 때문이다.
input입력 갯수만큼 반복해서 받아주고
해당하는 index = 즉, 숫자에 해당하는 count가 존재한다면, 그 횟수만큼 반복하여 숫자를 출력해준다.
그럼 순서대로 나오게 된다!