[BOJ] 10989 - 수 정렬하기 3

엄혜영·2024년 3월 21일

algorithm boj

알고리즘 챌린저까지

목록 보기

5/11

지금까지 이런 적은 없었는데...

이번 문제는 메모리 제한이 있는 문제이다.

시간 제한은 5초로 나름 넉넉하지만, 메모리 제한이 있는데다가

많은 개수의 입력이 들어오는 문제이다.

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

문제의 코드

일단 무지성으로 하던대로 풀어봤다.

입력받는 숫자는 중복이 가능하고 출력은 정렬이 되어야 한다.

입력값을 리스트로 받은 뒤 sorted()로 정렬하여 출력하였다.

import sys

repeat = int(input())
numbers = []
for i in range(repeat):
    numbers.append(int(sys.stdin.readline()))

snumbers = sorted(numbers)
for i in snumbers:
    print(i)

근데 이렇게 제출하면 메모리 초과가 난다.

솔직히 원인은 정확히 모르겠고, 입력받는 수의 개수가 최대 10,000,000이기 때문에 이게 문제이지 않을까 싶었다.

중복이 되지 않으므로 입력받을 때마다 길이가 길어지니까.

개선한 코드

그래서 딕셔너리 자료구조를 생각해냈다.

key로 입력받는 숫자를 넣고, value로 그 숫자가 들어온 개수를 표현하면 되니까.

그러면 리스트로 구현했을 때처럼 입력받는 개수만큼 메모리 공간을 할당 해야되는 일은 없을 것이다.

입력값이 10,000보다 작거나 같으므로 딕셔너리의 길이도 최대 10,000개로 보장되어 있다.

import sys

repeat = int(input())
numbers = {}
for i in range(repeat):
    num = int(sys.stdin.readline())
    if num in numbers:
        numbers[num] += 1
    else:
        numbers[num] = 1

snumbers = sorted(list(numbers.keys()))
for i in snumbers:
    iCount = numbers[i]
    for j in range(iCount):
        print(i)

결론적으로 통과는 했는데 한 가지 의문이 생겼다.

다른 사람들이 제출한 것과 내 것이 실행 시간에서 차이가 많이 난다.

메모리는 비슷하다 쳐도 실행 시간이 압도적으로 길다.

대체 왜..???

한 단계 더

문제를 더 효율적으로 풀 수 있는 방법이 있는 것 같아 구글링을 해봤다.

참고자료에도 써놓았지만 아래 코드는 윤상ol님의 글을 참고하였다.

for 문 속에서 append를 사용하게 되면 메모리 재할당이 이루어져 메모리를 효율적으로 사용하지 못한다고 한다.

따라서 num_list = [0] * 10001 로 값이 0으로 초기화된 리스트를 만들어 놓는다.

리스트에 각 요소마다 0을 할당해놓고 입력값을 받을 때마다 그 입력값과 같은 인덱스에 +1씩 해준다.

이후 입력을 다 받고나면 0보다 큰 요소를 갖는 인텍스를 찾아서 그 수만큼 인덱스 값을 출력해주면 된다.

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 메모리 재할당에 대해서 더 알아봤다.

정확히 말하자면, append를 할 때마다 추가 공간을 할당하는 것은 아니고, 일정 패턴으로 할당하는 사이즈가 증가된다.

( 사실 아래 그림도 완전히 정확한 표현은 아니고 간략하게 표현한 것이다.

리스트의 메모리 구조에 대해서 더 공부하고 싶다면 이 블로그를 참고해보자. )

다시 돌아와서, 리스트 메모리 구조를 그림으로 대강 표현하자면 아래와 같다.

append를 사용해서 값을 추가하는 경우

mylist가 선언되었을 때는 빈 공간을 가리키고 있는다.

이후 mylist.append(1)로 값을 추가해주면 내부에서는 공간을 새로 할당하여 그 곳에 1 객체를 연결해준다.

할당받은 공간을 다 사용할 때 까지는 값을 단순히 연결해주기만 하면 된다.

할당받은 공간을 다 사용한 뒤 리스트에 값을 더 추가하려면 메모리 공간을 재할당 받아야 한다.

공간을 재할당 받은 뒤의 동작은 위의 과정과 동일하다.

대괄호로 바로 값을 집어넣는 경우

list(range(n))과 [m]*n도 동일하다.

선언한 개수만큼만 메모리 공간을 할당한다.

비교

import sys

# 빈 리스트 생성
my_list = []

# 10부터 100까지의 정수를 리스트에 추가하면서 메모리 사용량 측정
for i in range(10, 101, 10):
    my_list.append(i)
    print(f"my_list size: {len(my_list)}, Memory usage: {sys.getsizeof(my_list)} bytes")
    
my_list2 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# my_list2 = list(range(10))
# my_list2 = [0] * 10
print(f"\nmy_list2 size: {len(my_list2)}, Memory usage: {sys.getsizeof(my_list2)} bytes")