[BOJ] 10989번: 수 정렬하기 3

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

Python3

수 정렬하기 2의 문제와 비슷해보였여 제출했던 코드를 그대로 제출해보았다.

https://miraekwak.tistory.com/72

[BOJ] 2751번: 수 정렬하기 2

역시나 실패! 메모리 초과가 떴다. 메모리 차이를 비교해보니 256MB가 8MB로 줄었다. 문제의 차이점을 살펴보면 입력받는 숫자의 최대 크기가 주어졌다는 것이다. 10,000보다 작거나 같은 자연수만 주어진다.

우선 이전 코드에서 메모리 차지를 많이 한 부분은 빈 리스트를 생성해놓고 append를 통해 삽입하는 과정에서 있다. for문 속에서 append를 사용하게 되면 메모리 재할당이 이루어져서 메모리를 효율적으로 사용하지 못한다. 이를 고치기 위해 10,000 숫자를 보고 10,000크기의 배열을 생성을 생각했다. 미리 10,000까지를 만들어놓고 해당하는 숫자의 인덱스만 증가시켜 나중에 인덱스만큼 출력을 해주면 되는 문제였다. 정렬 문제이긴 하지만 참신한 방식의 정렬이라 신기했다.

 

import sys
if __name__ == '__main__':
    N = int(input())
    numbers = [0]*10001
    for _ in range(N):
        numbers[int(sys.stdin.readline())] += 1
    for i in range(10001):
        if numbers[i] > 0:
            for _ in range(numbers[i]):
                print(i)

0번째 인덱스는 빼기위해 10001 크기로 만들었다. 중요한건 카운트된 만큼 해당 숫자를 출력해주어야 한다는 것!