백준 7569 토마토
코딩테스트 스터디에서 코드 발표 중 나온 의문
어떤 의문인지는 코드를 먼저 보고나서!
정답 코드
import sys
# 이 문제에서는 deque을 안 쓰면 시간초과가 납니다
from collections import deque
input = sys.stdin.readline
M, N, H = map(int, input().split())
tomato_info = [[] for _ in range(H)]
ripen_tomato = deque([])
# 토마토 지도와 익은 토마토 덱 세팅
for h in range(H):
for n in range(N):
row_info = list(map(int, input().split()))
tomato_info[h].append(row_info)
for m in range(M):
if tomato_info[h][n][m] == 1:
ripen_tomato.append((m, n, h))
dm = [-1, 0, 1, 0, 0, 0]
dn = [0, 1, 0, -1, 0, 0]
dh = [0, 0, 0, 0, 1, -1]
# 익은 토마토를 시작으로 BFS
'''
함수 처리 해보기
'''
def make_ripen():
while ripen_tomato:
m, n, h = ripen_tomato.popleft()
for i in range(6):
newM, newN, newH = m+dm[i], n+dn[i], h+dh[i]
# 범위 내에 토마토가 아직 안 익었으면 익히기(== 이전 위치의 토마토의 것에서 날짜 수 +1)
if 0 <= newM < M and 0 <= newN < N and 0 <= newH < H:
if tomato_info[newH][newN][newM] == 0:
ripen_tomato.append([newM, newN, newH])
tomato_info[newH][newN][newM] = tomato_info[h][n][m] + 1
make_ripen()
day = 0
for plate in tomato_info:
for row in plate:
for tomato in row:
# 다 돌았는데 아직 익지 않은 게 있다면 결국 익지 않는 경우의 수이므로
if tomato == 0:
print(-1)
exit()
# 한 줄을 검사했을 때 가장 일자가 긴 것이 전체 토마토를 익히는 일자
day = max(day, max(row))
# 익은 토마토가 1로 시작하므로 걸린 일자는 1 빼줘야함
print(day -1)다소 어렵지만 기본 BFS에다가 누적을 잘 통제하면 금방 풀리는 문제였다.
그런데 여기
BFS 돌릴 ripen_tomato의 초기화를 deque([])으로 했는데,
왜 이렇게 했냐? 묻는다면
이전에 deque()로 했다가 append 오류가 난 적이 있어서 빈 배열로 초기화를 쓴 것이다.
그런데 정확한 차이는 몰랐기에 분석할 겸 글을 쓰게 됐다.
시간 비교
정수 리스트
from time import time
from collections import deque
# 덱에 정수 넣기
start = time()
test01_start = time()
test01 = deque()
for i in range(100001):
test01.append(i)
print('diff', time()-test01_start)
# diff 0.009357929229736328
test02_start = time()
test02 = deque([])
for j in range(100001):
test02.append(j)
print('diff', time()-test02_start)
# diff 0.01008296012878418
# -> 9ms 10ms 1ms 차이가 납니다
# 덱에 리스트 넣기
test03_start = time()
test03 = deque()
for i in range(100001):
test03.append([i, i+1, i+2])
print('diff', time()-test03_start)
# diff 0.030982017517089844
test04_start = time()
test04 = deque([])
for j in range(100001):
test04.append([j, j+1, j+2])
print('diff', time()-test04_start)
# diff 0.03740811347961426
# -> 309ms 374ms 70ms 차이가 납니다각각 정수를 넣을 때와 리스트를 넣을 때의 시간을 구해봤는데,
큰 차이는 아니지만 어느정도 시간차가 나는 것을 보면 동일하게 작동하는 코드는 아닌 것을 알 수 있다.
도마도의 경우
<deque() vs deque([]) 차이>
deque() -> 50864KB 3360ms
deque([]) -> 50840KB 3240ms
무조건 빈 초기화로 하는 게 시간이 적게 걸리는 건 또 아니었다.
그래서 어떤 게 차이일까 하고 찾아보았다.
operation 비교
testQ1 = deque([1, 2, 3])
print(testQ1.popleft())
# 1
testQ2 = deque()
testQ2.append([1, 2, 3])
print(testQ2.popleft())
# [1, 2, 3]
testQ3 = deque([])
testQ3.append([1, 2, 3])
print(testQ3.popleft())
# [1, 2, 3]각 operation 별 시간은 다음과 같다
| case | time |
|---|---|
| testQ1 | 3.0994415283203125e-05 |
| testQ2 | 7.867813110351562e-06 |
| testQ3 | 5.7220458984375e-06 |
testQ1는 미리 초기화를 시킨 것,
testQ2는 deque(),
testQ3는 deque([])으로
각각 append시킨 것이다.
시간은 deque([])<deque()<deque([1, 2, 3]) 순이나 차이를 따지면 큰 의미는 없다.
다만 주의해야할 점은 [] 빈 배열로 초기화 시키는 것과
[1, 2, 3] 이렇게 값이 들어가 있는 배열로 초기화 시키는 것에 있어서
구성이 달라진다는 것을 알아둬야한다.
testQ1 = deque([1, 2, 3])
testQ2 = deque([[1, 2, 3]])
testQ3 = deque([[1, 2, 3]])이 때문에 testQ1과 testQ2, testQ3 간의 popleft 결과 차이가 나는 것이다.
결론
얼마나 시간이 걸리는지 다양한 경우에 따라 비교해보았는데,
경향성을 찾을 수 없었다.
따라서 deque(), deque([]) 간에 의미는 사실상 큰 차이가 없다고 판단했고,
이후 어떤 operation을 쓰는가에 따라
또는 빈 배열이 아니라 다른 값으로 초기화하려 할 때 원하는 형태로 가는지 잘 확인하고 써야함을 인지해야 한다.
