[백준/Python] 10989번 수 정렬하기 3 문제

■ 10989번 수 정렬하기 3 문제

 

출처: 백준 10989번 수 정렬하기 3 문제

 

 

■ 코드 풀이

 

백준 문제를 풀면서 처음 메모리 초과를 경험했습니다. 아무래도 코딩을 독학하고 취미로 하다 보니, 메모리에 대한 고려를 많이 못했던 것 같습니다. 그러다 보니 코드를 어떻게 작성해야 하는지 몰라서 다른 분께서 푸신 것을 참고했습니다. 원본 코드 링크는 아래 글 참고해 주세요.

 

https://pacific-ocean.tistory.com/67

백준 알고리즘 10989번(python 파이썬)

 

아래 코드의 핵심은 list에 새로운 값을 'append'하지 않는 것입니다. append를 하게 되면 메모리 재할당이 발생하여 메모리를 많이 잡아먹는다고 합니다. append를 하지 않고 어떻게 푸느냐... 우선 입력되는 숫자는 최대 10,000보다 작거나 같은 자연수라고 문제에서 주어졌습니다. 그래서 0으로 초기화된 길이 10,001짜리 list를 먼저 만들어줍니다. 참고로 길이가 10,001개인 이유는 list의 index는 0부터 시작하지만, 숫자는 1부터 주어지므로 편의성을 위해서입니다.

그리고 입력받은 값을 int로 변환하여 list에 indexing 하여 count를 해줍니다. 모든 입력이 끝나면 list에는 1부터 10,000까지 자연수가 각각 몇 번 입력받았는지에 대한 결과 값이 저장되어 있게 됩니다. 이후 for문을 활용하여 count 된 개수만큼 해당 index를 반복적으로 출력하면 됩니다.

이 코드에서 배울 점은 최대 천만 개의 숫자를 길이가 만개정도밖에 되지 않는 리스트로 처리했다는 점입니다. 이런 메모리 활용은 생각지도 못했네요. 역시 고수들은 많은 것 같습니다. 

 

import sys

n = int(sys.stdin.readline())
num_list = [0] * 10001

for _ in range(n):
    num_list[int(sys.stdin.readline())] += 1

for i in range(10001):
    if num_list[i] != 0:
        for j in range(num_list[i]):
            print(i)

 

참고로 파이썬 append의 메모리 관련 내용은 아래 링크를 참고했습니다.

 

https://wikidocs.net/21057

10_메모리 관련