[백준] 10989 수 정렬하기 3

#백준 10989 수 정렬하기 3

1.  시간초과 코드

n = int(input())
result = []
for i in range(n):
    a = int(input())
    result.append(a)
result.sort()

for i in range(n):
    print(result[i])

- for문 속에서 append를 사용하게 되면 메모리 재할당이 이루어져서 메모리 사용이 비효율적이다

출처 : https://wikidocs.net/21057

이 문제는 시간&메모리 제한이 엄격하기 때문에 이 점을 고려하여 10000크기의 배열을 선언해주어 배열만큼의 메모리만 사용하도록 코드를 변경하였다.

 

2. [0]*10001 배열 사용

import sys

N = int(input())
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)

1. 10001만큼의 배열을 만들어준다.

2. 배열의 인덱스가 입력숫자로 쓰이면서 나온 횟수만큼 더하기된다.

3. 1부터 10000까지 for문을 실행하며, nums[i]가 0이 아니면(즉, 한 번이상 나온 숫자) 나온 횟수만큼 i를 출력