[백준] Python 시간초과 해결 방법

최근에 백준 문제풀이를 하면서 시간초과가 자주 발생했다.

문제 난이도가 조금씩 올라갈수록 시간제한과 메모리를 고려하면서 풀어야한다.

 

이번 게시물은 daily_D님의 게시물을 참고하여 작성한 것이다.

https://dailylifeofdeveloper.tistory.com/182

[Python] 시간 초과 날때 해결방법!

해당 글에는 시간초과가 발생했을 때, 어떻게 해결하면 좋을지 고민하면서 궁금했던 내용이 잘 정리되어 있어서

참고하여 작성해두고, 필요할 때마다 보려고 한다!

 

* Python의 경우만 다루었다.

 

 

 

---

 

1. sys.stdin.readline()로 입력받기

입력값을 받아야 하는 경우, 보통 input()으로 구현하지만,
sys 라는 Python 표준 라이브러리를 사용하면 훨씬 빠르게 적은 메모리를 사용하여 입력을 받을 수 있다.

실제로 문제를 풀면서 실험을 해보았는데, 유의미한 시간 차이가 발생해서 input을 어떻게 받았느냐에 따라 성공/실패가 갈리기도 했다.
그래서 웬만하면 해당 라이브러리를 사용하는 편이다.

import sys 
변수 = sys.stdin.readline()

 

2. 배열에 원소 추가할 때 인덱스로 접근하기

배열에 원소를 추가하는 경우, 보통 빈 배열을 선언해두고 필요할 때마다 append()로 추가하는 경우가 많은데,
이때 입력 받을 개수(N)를 알고있다면 크기가 N이 되도록 배열을 초기화해두고, 필요할 때 인덱스로 직접 접근해서 저장하는 것이 효율적이다.

이건 평소에 문제를 풀면서 실제 차이가 있을지 궁금했던 부분인데, 인덱스 접근을 많이 활용하는 것이 좋겠다.

# append() 사용
arr = []
for num in range(N):
    arr.append(num * 5)
    
# 인덱스 접근 2가지 방법
arr = [0 for _ in range(10)]
arr2 = [0] * N # 파이썬은 * 방식으로도 선언 가능하다
for num in range(N):
    arr[num] = num * 5

 

3. 줄바꿈을 출력해야하는 경우 문자열로 바꿔 출력하기

줄바꿈이 자주 반복된다면 print()보다 '\n' 사용하는 것이  좋다.
그렇기 때문에 문자열 변수에 정답을 저장해놓고 한 번에 출력하는 것이 효율에 좋다.

# 매번 출력하기
arr = [1, 2, 3, 4]
for num in arr:
    print(num)
    
# '\n'을 사용해서 한 번만 출력하기
answer = ""
for num in arr:
    answer += str(num) + '\n'
print(answer)

 

추가 정보 - 출력

이것 말고도 추가적으로 출력할 때 유용한 팁을 적자면,

배열에 담긴 숫자를 출력할 때에는 [], 같은 문장부호 없이 숫자들만 띄어쓰기를 포함해서 출력해야 하는 경우가 있다.

예를 들어, [1, 2, 3, 4] 의 배열을 1 2 3 4 로 출력하고 싶은 경우가 있다. 

for문을 사용해서 출력하거나 위의 코드와 유사하게 ' '를 추가하여 출력하는 방법이 있을 수 있지만, 배열 앞에 * 연산자를 붙여서 출력하면 쉽게 출력할 수 있다.

# 1. 그냥 출력하는 경우
arr = [1, 2, 3, 4]
print(arr)
# 결과 : [1, 2, 3, 4]

# 2. * 사용해서 출력하는 경우
print(*arr)
# 결과 : 1 2 3 4

이것의 원리를 살펴보면, 배열 앞에 * 연산자를 붙여서 함수를 호출하면 마치 여러 개의 인자를 넘긴 효과가 나고,
기본적으로 print() 함수는 공백을 구분자로 하여 출력하기 때문에 가능한 것이다.

 

또한, 파이썬 연산자 *와 함께 print() 함수의 sep 옵션을 사용하면 더욱 유용하게 활용할 수 있다.

sep 옵션으로 구분자를 바꿔줄 수 있다.

>>> arrs = [[0, 1, 2, 3, 4, 5], [6, 7, 8, 9, 10, 11]]
>>> print(*arrs, sep='\n')
[0, 1, 2, 3, 4, 5]
[6, 7, 8, 9, 10, 11]

>>> print(1, 2, 3)
1 2 3
>>> print(1, 2, 3, sep=',')
1,2,3
>>> print(1, 2, 3, sep='\n')
1
2
3

 

4. 재귀 깊이 늘려주기

파이썬은 기본적으로 재귀호출을 1000번으로 제한하고 있기 때문에 더 많은 재귀를 요구할때는 재귀깊이를 늘려주어 사용해야 한다.

이건 처음 알게 된 내용!

import sys
sys.setrecursionlimit(1000000) #1000000번 재귀가 가능하도록 변경하기

 

5. queue 로 구현할 때 리스트보다  deque 사용하기

Python 에서는 리스트보다 collections.deque 모듈을 사용하는 것이 더 빠르기 때문에 Queue 를 통해 문제를 해결해야하는 상황이 있다면 deque 를 사용하는 것이 시간이 단축된다

 

queue는 보통 자료구조 문제나 BFS 문제를 풀 때 사용하게 되는데, collections의 deque가 매우 유용하다.

심지어 시간까지 빠르니 잘 기억하고 써먹어야지 !

from collections import deque

queue = deque()
for i in range(N):
	queue.append(i)
for i in range(N):
	queue.popleft() # 왼쪽(앞)부터 꺼내기

---

위의 방법들로 시간초과를 해결할 수도 있지만 항상 해결되는 것은 아니고
알고리즘을 수정해야 풀리는 문제들이 더 많으니 참고해주세요! ㅎㅎ

 

라고 하셨다 🙃