[Python] 백준 10989 메모리 초과와 시간 초과

백준 문제를 풀어나가다 10989번 문제를 접했다.

 

 

문제는 상당히 간단해 보이지만 조건을 보면 시간과 메모리 제한이 까다롭게 걸려있다.

간단하게 문제를 해결해보기 위해 기존에 풀던 방식으로 접근했다.

n = int(input())
nums = []
for i in range(0, n):
    nums.append(int(input()))
nums.sort()
for j in range(0, n):
    print(nums[j])

 

결과는 메모리 초과 - > 메모리 초과가 뜨는 이유는 무엇일까?

메모리 초과가 뜨는 이유는 대부분 stack overflow 때문이라고 한다.

이 경우에 따르면 아마 입력받는 모든 수를 리스트에 추가해 버리기 때문에

리스트가 무한정 커져 버리기 때문에 그런 것 같다.

---

# 메모리 초과 해결방안

한 블로그 에서 이러한 문제를 해결하기 위해 계수 비교라는 방법을 사용했다.

이 코드는 입력받을 수 있는 숫자의 최대값 (10000) 만큼의 인덱스를 가지는 리스트를 선언해주고, 0으로 초기화한다.

이 부분에서 전에 내가 제출한 코드보다 사용되는 리스트의 크기가 확 줄어들었기 때문에 메모리 초과 문제가 해결된 듯하다.

숫자를 입력 받을 때마다 해당 arr[숫자] 를 1씩 올려서, '숫자' 인덱스값을 가지는 인덱스의 값이

'숫자' 의 개수를 표현할 수 있도록 한다.

import sys

n = int(sys.stdin.readline())
arr = [0] * (10000 + 1)
for i in range(n):
    num = int(sys.stdin.readline())
    arr[num] += 1
for i in range(len(arr)):
    if arr[i] != 0:
        for _ in range(arr[i]):
            print(i)

 

그리고 마지막으로는 반복문을 통해 요솟값이 0이 아닌 요소들의 인덱스값을 요솟값만큼 반복해서 출력해주면 원하는 결과를 얻을 수 있었다.

---

# 시간 초과 해결방안 (실제로 시간 초과가 뜨지는 않았지만 염려되어서 바꿈)

또한 sys 모듈을 사용한 이유는 input()을 사용할 때보다 sys.stdin.readline()을 사용할 때 더 적은 시간이 걸리기 때문이다.

input()은 prompt message와 함께 입력받고, 입력받은 값을 하나하나 버퍼에 저장한다는 특징이 있어서 sys.stdin.readline() 보다 처리 속도가 느리다.

sys.stdin.readline()은 반면 한 줄씩 읽어 버퍼에 저장한다. 다만 개행문자까지 읽어들인다.

 

참고문을 보면 다소 소소한 차이점이 둘 사이에 존재하지만, 둘 중에 무엇을 쓸지 심각하게 고려하지 말라는 답변 필자의 말을 듣고 상황에 따라서 유도리있게 input() 과 sys.stdin.readline() 을 쓰면 될 것 같다.

---

# 참고

https://stackoverflow.com/questions/22623528/sys-stdin-readline-and-input-which-one-is-faster-when-reading-lines-of-inpu#:~:text=input%20will%20raise%20an%20EOFError,closed%20on%20the%20other%20end