[Python] 백준 10989번 수 정렬하기 3 /메모리 초과 오류 해결

 

import sys
input = sys.stdin.readline

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

for i in arr:
  print(i)

입력받은 값을 빈 배열 arr에 append 후, sort()함수로 오름차순하여 출력하는 형식을 생각했다

하지만 메모리 초과 발생...!

메모리 제한이 8MB로 굉장히 작은데,  많은 메모리를 소요하는 파이썬으로 실행하니 쉬운 문제임에도 불구하고 오래 걸렸다....

메모리 초과 발생 이유

(1) sort,sorted를 사용

(2) sys.stdin.readline이 아닌 그냥 input()를 사용

(3) for 문 안에 append를 작성

 

따라서 이 문제는 계수정렬를 사용해야한다.

 

계수정렬을 알고 싶으면 내가 쓴 게시물을 참고하자

https://kill-xxx.tistory.com/entry/python-%EA%B3%84%EC%88%98%EC%A0%95%EB%A0%AC

 

 

 

전체코드

import sys
input = sys.stdin.readline

#계수정렬 활용
n = int(input())
arr = [0] * (10000 + 1) # 입력값이 10000개까지 주어지니 10000 + 1개의 리스트 선언

#각 입력값에 해당하는 인덱스의 값 증가
for _ in range(n):
    arr[int(input())] += 1
  
#arr에 기록된 정보 확인
for i in range(len(arr)):
    if arr[i] != 0: #0이 아닌 데이터, 즉 입력받은 데이터들을 출력
        for _ in range(arr[i]):
            print(i)

 

(1) 리스트를 [0] * (데이터의 길이 + 1)만큼 선언한다.

arr = [0] * (10000 + 1)

arr [0 ,0, 0, 0,......] 10001개의 인덱스 생성

 

(2) 입력값을 받을 때마다 그 입력값과 같은 인덱스에 +1 추가

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

1 1 1 3 2 1을 입력 받았다면 1이 4개, 2가 1개, 3이 1개 이므로

arr[0,4,1,1]이 될 것이다 

 

(3) 입력이 끝나면 0이 아닌 인덱스를 찾아 그 수만큼 인덱스를 출력해주면 된다.

for i in range(len(arr)):
    if arr[i] != 0:
        for _ in range(arr[i]):
            print(i)