백준 10989번 수 정렬하기 3 파이썬 풀이

[Python] 백준 알고리즘 온라인 저지 10989번 수 정렬하기 3

10989번 수 정렬하기 3

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

10989번: 수 정렬하기 3

저번 문제에서는 빠른 연산이 필요했다면 이번 문제에서는 메모리를 적게 차지하는 방법을 찾아야 했다. 수 정렬하기 2번에서는 256 MB의 메모리 값을 사용 가능했지만 여기서는 8 MB뿐이다. 

---

코드

import sys
n = int(sys.stdin.readline())
nums = [0] * 10001
for _ in range(n):
    nums[int(sys.stdin.readline())] += 1
for i in range(10001):
    if nums[i] != 0:
        for j in range(nums[i]):
            print(i)

---

풀이

수 없이 많은 메모리 초과와 시간 초과로 스트레스를 받고 다른 분들의 코드를 참조하기로 마음을 먹었다.

빠른 연산을 위해 sys 모듈을 사용하는 것은 저번 백준 2751번 수 정렬하기 2 파이썬 풀이에서 다뤘으니 넘어가고 메모리를 적게 사용하는 방법에 대해 생각 해야 했다. 위의 방법은 0을 값으로 가지는 길이 10001개의 배열(nums)을 만들어 이 배열의 인덱스 값(순서)을 이용하여 답을 출력하는 방법이다. (10000개의 배열을 만드는 이유는 10000보다 작거나 같은 수라고 명시했기 때문)

모두가 알다시피 배열은 0부터 시작하므로 + 1을 하여 입력 값들을 받아준다. 만약 1, 2, 3, 4, 1의 값을 받았다고 가정하면 입력 값을 받은 nums는 [0, 2, 1, 1, 1, 0, 0....0]로 저장됩니다.

이 배열을 이용하여 for문으로 10000까지 i 값이 돌도록 하고 if문으로 nums의 i번째 배열의 값이 0이 아니라면 그 i를 출력하도록하고 두 개 이상인 경우를 생각하여 for문을 다시 한번 사용하고 nums의 i번째 배열의 값만큼 반복하여 출력한다.

---

 풀이 결과

풀이 결과