백준 BOJ 시간초과 팁 (부제: 우리의 시간은 소중하니까)

백준 시간초과

백준에서 알고리즘 공부를 하다보면 시간초과로 애를 먹을 때가 많다. 시간초과 문제 고치다가 내 시간만 초과되는 상황..

막상 다 풀어보면 분명 다른 사람들과 몇 줄 차이 안나는데 시간차이가 많이 나는게 마음에 안들어서 도대체 뭐가 다른지 찾아봤다.

 

시간초과 때문에 가끔 다 때려치고 싶을 때가 있다

 

우리 모두의 시간은 소중하니까 시간을 단축할 수 있는 방법들 중 몇 가지를 가져왔다.

 

1. input()보다 sys.stdin.readline()이 더 빠르다.

백준 문제를 많이 풀어본 사람들은 많이 아는 팁이다.

 

input() 내장함수

word = input("단어를 입력해주세요")

input이 호출되면 Promt message를 화면에 출력하고 사용자의 입력을 기다린다. 사용자가 키를 하나씩 누루면 데이터가 버퍼에 들어가는데, 개행문자(줄바꿈;enter)가 입력되면 버퍼의 입력이 종료되는 것으로 간주한다.

 

sys.stdin.readline()

word = sys.stdin.readline()

이와 달리 sys.stdin.readline()는 promt message을 파라미터로 받지 않으며 개행 문자를 포함하여 한번에 읽어와 버퍼에 보관하고 사용자가 요구할 때 버퍼에서 읽어오게 하는 것이다.

 

결론적으로,

input() 내장함수는 Promt 문자열을 화면에 출력하고 character단위로 읽어들이며 개행문자를 삭제시켜 값을 리턴하기 때문에 훨씬 느리다!

 

따라서 입력 값에 promt message가 필요없는 BOJ에서 시간 초과가 났을 때, sys입력으로 변경해주면 정답처리가 될 확률이 크다.

 

+ 코드 위에 추가하면 편하다.

import sys
input = sys.stdin.readline

 

2. if문에 두 개 이상의 조건이 주어질 때, 조건의 순서를 생각하면서 작성한다.

if condition1 and condition2:

논리연산이 and인 경우 condition 중에서 False값을 많이 가진 condition을 앞에 오도록 하면 뒤에 오는 condition에 대한 확인 작업을 피할 수 있다.

 

if condition1 or condition2:

논리연산이 or 인 경우 True값을 많이 가진 condition을 앞에 오도록 하면 뒤에 오는 condition에 대한 확인 작업을 피할 수 있다.

 

3. 문자열을 붙일 때 +연산 대신 join()을 사용한다. 

+ 연산을 하는 경우 각각 문자열을 새로운 메모리 공간에 복사하여 작업을 수행하는데, join()을 사용하게 되면 미리 총 메모리 공간을 계산한 뒤 필요한 메모리를 확보하고 각각 문자열을 복사하기 때문에 더 빠르다고 한다. 

## + 연산
for str in string_list:
	concatenate_string += str

## join()함수
concatenate_string = "".join(string_list)

 

4. List Comprehension을 사용한다.

for 루프를 한줄로 축약하여 표현하는 방법인데, 기본 for loop보다 속도가 더 빠르다고 한다.

## for loop
numbers = []
for i in range(1000):
	numbers.append(i)
    
## comprehension
numbers = [i for i in range(1000)]

 

+ 배열을 만들때 for loop을 돌리는 것보다 multiplication으로 할당하는 것이 빠르다!

코딩테스트 스터디 단톡방에서 얻은 팁 (팁 제공자: JBJ님)

 

스터디 단톡방에서 시간 복잡도에 대해서 얘기하다가 얻은 팁으로,

for loop을 도는 것보다 multiplication으로 할당하는 것이 빠르다.

 

+ BFS을 사용할 때 많이 만들어본 노드 방문여부 배열을 생성할 때 유용하다!

visited = [[False]*(N) for _ in range (M)]

visited = [[False for _ in range(N)] for _ in range(M)]

 

++ 직접 확인해본 결과, 훨씬 빠르다는 것을 볼 수 있었다.

 

[참고]

유용한 파이썬 문법(Useful Skill)

[Python] input보다 sys.stdin.readline의 처리 속도가 빠른 이유는?

[Python] 입력 받기(input VS sys.stdin.readline 차이점)