[algorithm] 백준 10989 - 수 정렬하기3

[algorithm] 백준 10989 - 수 정렬하기3

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 10989번 문제 - 수 정렬하기3 의 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 10989

 

백준 10989번 수 정렬하기3 문제 보러가기

 

반응형

 

문제 해석

 

저번에 같이 풀었던 문제 2751번 수 정렬하기2 와 비슷한 문제이지만 이번 문제에서는 메모리 사용량을

신경써주어야하는 문제입니다.

우리는 파이썬을 사용해 문제를 풀 것이기 때문에 내장함수를 잘 이용하면 좋겠죠??

 

메모리 초과된 풀이

 

# 10989 수 정렬하기3 메모리 초과 뜸

n = int(input())

list = [int(input()) for _ in range(n)]

list.sort()

for i in list:
    print(i)

 

통과된 풀이

 

# 10989 수 정렬하기3

import sys

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

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

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

 

풀이 해석 및 팁

 

처음에 메모리 초과된 풀이를 살펴보면 리스트를 만들 때 comprehension방식을 사용해서 나름 메모리 초과를

신경써주었지만 그래도 메모리가 초과되는 상황이 생겨버렸습니다.

입력값의 개수는 최대 10,000,000개 까지이고 입력값의 최대 크기는 10,000이라는 조건이 주어집니다.

리스트에 요소가 너무 많이 추가되어서 메모리가 초과된 것으로 보입니다.

이를 해결하기 위해서 풀이 방식을 아예 다른 방식으로 전환했습니다.

입력값의 최대 크기가 10,000 이기때문에 0을 10,000개 가지고있는 리스트를 만든 후

입력값이 들어오면 그 값을 리스트의 인덱스에 넣어주면서 해당 요소의 값을 1씩 늘려줍니다.

입력값을 모두 처리했으면 리스트에서 0이 아닌 요소들을 찾아서 해당 인덱스를 요소의 값 만큼 출력해줍니다.

위 과정으로 정렬을 하지 않고 오름차순으로 정렬한 효과를 볼 수 있습니다.

---

여기까지 백준 10989번 수 정렬하기3 문제 풀이였습니다.

 

정답률이 23%인 것으로 보아 대부분 메모리초과로 인한 실패로 보입니다.

 

메모리를 신경쓰면서 코딩하는것은 하드웨어적으로 제한이 있는 상황에서는 꼭 필요한 과정입니다.

 

평소에 코딩을 할 때 메모리 사용량을 신경쓰면서 코딩해보는건 어떨까요?

 

감사합니다.