[ BOJ 오답노트 ] 10989 파이썬 : 수 정렬하기 3

2022 02 28

 

1. 틀린 기록

 

 

 

2. 원인 분석

- 메모리 초과가 떴다. 아무래도 입력되는 모든 숫자들을 저장하는 방법으로 풀면 최대 입력 개수인 10000000 크기의 리스트가 필요하기 때문에 메모리 초과 판정을 받은 것 같다.

- 그래서 생각한 방법은, 중복적으로 들어오는 값을 횟수만큼 저장하는 것이 아니라, 입력될 수 있는 가장 작은 숫자인 1부터 입력될 수 있는 가장 큰 숫자인 10000을 저장할 수 있는 리스트를 미리 만들어 두는 것이다.

- 이 리스트를 0으로 초기화하고, 나오는 개수만큼 +1 해주어서 입력된 횟수만큼 반복해서 출력해주는 방식으로 정렬하는 것이다.

- 이 방법은 굳이 sort() 를 사용하지 않아도 된다는 점과 리스트의 크기를 줄일 수 있다는 점에서 유용한 방식이라고 생각했다.

 

 

 

3. 해결

import sys
input = sys.stdin.readline

lst = [0] * 10001

for _ in range(int(input())):
    lst[int(input())] += 1

for i in range(1, len(lst)):
    for j in range(lst[i]):
        print(i)

- lst 함수를 만들어서 1 ~ 10000 숫자들이 입력된 횟수를 저장할 수 있도록 했다. 

- 입력 값을 하나씩 받으면서 입력 받은 값에 해당하는 인덱스 값의 원소를 +1 해준다. (횟수를 의미한다.)

- 이중 for문을 사용해서 lst의 원소들을 하나씩 검토하고, 그 원소 값들 만큼 반복 출력해준다.

 

 

 

4. 배운 점

- sort를 직접하지 않고 배열의 리스트에 횟수를 저장하여 반복 출력하는 방법을 배워보았다.

- 지금까지는 Timeout을 막기 위한 정렬 방법에 대해서만 고민해보았는데, memory 초과를 막기 위한 정렬 방법에 대해서도 생각해보게 된 문제였다.