boj-10989(Counting_Sort_Variation without Original_Array)

白準10989号を解いて、苦労したところを書きたいです.
まず,入力数が最も多い値は1000000であるため,単純な計算のみである.
int型4 Byte*1000000=400000バイト=40 MB、
これはメモリ制限8 MBをはるかに超えます.
ということで最初はCounting Sortを利用していましたが、簡単に書けましたがメモリが限られていたので、なぜか考えてみました
これは,入力しようとしないinputnumberがリストに格納されているためである.ううう
だから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')

そして,コードを記述して説明しようとする過程で,累積を格納しsord 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に入力された数字に対応する数字を増やして繰り返し出力するので,この過程は意味のない過程と解釈される.面倒くさいから...削除していません...
すべてのコードを整理すると

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なのでMAXNUM変数に格納されます.
入力numの数を受け入れ,count生成の数はMAXNUMの数より1つ多い.
countのindexビットの対応する数字が使用されるからです.
入力された数だけ繰り返し受け入れます.
対応するindex=すなわち、数字に対応するcountが存在する場合、その回数を繰り返して数字を出力する.
それでは順番に出ます!