시간 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='')
