백준 10989번 파이썬 풀이: 수 정렬하기 3

백준 1003번 수 정렬하기 3

 

알고리즘 분류: 정렬

 

링크: www.acmicpc.net/problem/10989

 

10989번: 수 정렬하기 3

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

 

문제 파악

 

사실 시간초과나 메모리 초과가 없다면 굉장히 쉬운 문제이다.

 

그러나 이번 문제에서 처음으로 메모리 초과를 겪어서 당황스러웠다.

 

시간초과를 겪는 경우는 많아서 시간복잡도를 줄이는 방법을 여러가지 써보는데

 

공간복잡도를 줄이는 방법은 많이 생각해보지 않았다.

 

메모리 초과를 줄이기 위해서 풀이방법을 검색하고 pacific-ocean.tistory.com/67 님의 풀이를 참고하였다.

 

 

코드

 

일단 정답 소스코드를 보기전에 메모리 초과가 난 틀린 코드를 보자면

# 10989번

import sys

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

for _ in range(n):
    num_list.append(int(sys.stdin.readline()))

sorted_list = sorted(num_list)

for i in sorted_list:
    print(i)

이게 메모리초과가 난 틀린 코드이다.

 

평소에 하는것처럼 빈 리스트를 만들어서 입력값을 하나씩 append하였다.

 

입력값을 다 받으면 이를 오름차순으로 정렬해서 하나씩 출력하는 코드를 짰는데

 

당연히 메모리초과로 틀렸다.

 

# 10989번

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)

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

 

일반적으로 입력값이 크지않은 경우에는 상관없지만 이렇게 입력값이 극한으로 많이 주어질 때에는

 

메모리를 좀 더 효율적으로 관리해야한다.

 

그래서 입력값이 10000개 까지 주어질 수 있으니 10000개 만큼의 리스트를 만들어 놓는다.

 

그러나 인덱스는 0부터 세기 때문에 이를 계산하기 편하게 길이가 10001인 리스트를 만든다.

 

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

 

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

 

파이썬은 내부적으로 연산과 메모리를 관리하기 때문에 파이썬에 내장되어있는 함수들을 적용할수록

 

메모리를 효율적으로 관리할 수 있다고 한다.

 

자세한 내용은 wikidocs.net/21057 에서 확인할 수 있다.