BOJ 1427 소트인사이드

시간 2초, 메모리 128MB

input :

• 정렬하고자하는 수 N (1 <= N <= 1,000,000,000)

output:

• 자리수를 내림차순으로 정렬한 수를 출력한다.

N 길이만큼의 리스트를 만들어서 내림차순 정렬을 하는 것은. 공간복잡도가 10억. 128MB 초과.
answer 리스트를 만들고 숫자들은 자연수의 범위안에서 존재한다.
N 숫자를 구성 하는 것은 (0 <= 자연수 <= 9)
answer를 길이 10까지 만들어 인덱스 마다 각 자연수가 몇 번 나왔는지 기록 한 후에 뒤에서 부터 각 요소 만큼 인덱스를 출력 하게 하자.

answer = [0] * 10

계수정렬 쓰듯.

10억의 숫자가 입력되면
10억. / 1억. / 1천만. / 1백만. / 십만. / 만. / 천. / 백. / 십. / 일.
최대 반복 10번.
for 문이 아닌 while문으로 N이 1보다 클 때 만 반복.

입력받은 숫자를 10으로 나눈 후 나머지 값을 기록. answer[나머지 값] += 1 한다.
입력 받은 숫자를 계속해서 10으로 나누고 나눈 값을 업데이트

while input_number >= 1:
    other = input_number % 10
    answer[other] += 1
    input_number = input_number // 10

출력시에 answerindex값만큼의 index에 대한 출력이 필요.

for i in range(len(answer) - 1, -1, -1):
    for _ in range(answer[i]):
        print(i, end='')

정답 코드:

input_number = int(input())
answer = [0] * 10
while input_number >= 1:
    other = input_number % 10
    answer[other] += 1
    input_number = input_number // 10

for i in range(len(answer) - 1, -1, -1):
    for _ in range(answer[i]):
        print(i, end='')