백준_python 10989번 수 정렬하기 3 (메모리 초과, 시간 초과)

<문제 링크>

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

10989번: 수 정렬하기 3

 

<정답 코드>

import sys
 
n = int(sys.stdin.readline())   # input()으로 입력 시 시간초과
 
nums = [0] * 10001
 
for _ in range(n):
    nums[int(sys.stdin.readline())] += 1    # 입력 값을 인덱스로 하는 위치에 1 더하기
 
for i in range(10001):
    if nums[i] != 0:    # 입력 값이 있으면
        for j in range(nums[i]):    # 8번째 줄에서 추가된 값의 횟수만큼 출력
            print(i)
 

 

 

코드 이해를 돕기 위한 input 후 nums 배열 상황 ↓

nums 배열

 

 

 

 

 1.  for문 내부에서 append로 배열에 값을 추가하는 방식으로 문제를 풀면,

for문 매 스텝마다 메모리 재할당이 일어나 메모리 초과 발생

=> 입력값을 인덱스로 갖는 배열에 값을 추가하는 방식으로 해결

 

 2.  입력하는 숫자의 최대 갯수가 크기 때문에(1 ≤ N ≤ 10,000,000) input()으로 입력을 받으면,

input()함수의 느린 속도로 인해 시간 초과 발생

=> input() 함수보다 빠른 sys.stdin.readline()로 해결

 

 

 

참고 자료 : https://wikidocs.net/21057