글 읽기 - [python3] 시간초과문제 ㅠㅠㅠ

bsy3719 4년 전 0

일단 테스트 케이스는 다 통과하는데 시간 초과가 뜹니다.

인터넷에서 찾은 파이썬 코드와 별차이없는데 왜 시간초과가 뜨는건지 궁금합니다.

n, m = map(int, input().split())
tomato = []

for i in range(m):
    temp_to = list(map(int, input().split()))
    tomato.append(temp_to)

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

q_cnt = 0
next_pos = []

for i in range(m):
    for j in range(n):
        if tomato[i][j] == 1:
            q_cnt= q_cnt + 1
            next_pos.append((i,j))

s_cnt = 0
while next_pos:
    x,y = next_pos.pop(0)
    value = tomato[x][y]
    
    s_cnt = s_cnt + 1
    for i in range(4):
        temp_x = x + dx[i]
        temp_y = y + dy[i]
        # 리스트의 사이즈가 더 큰 경우        
        if temp_x < 0 or temp_y < 0 or temp_x >= m or temp_y >= n:
            continue
            
        temp_value = tomato[temp_x][temp_y]
        
        # 벽    
        if temp_value != 0:
            continue
            
        if temp_value == 0:
            tomato[temp_x][temp_y] = value + 1
            next_pos.append((temp_x, temp_y))        
            
flag = False

for x in tomato:
    if 0 in x:
        flag = True
        break

if q_cnt == s_cnt:
    print(0)
elif flag:
    print(-1)
else:
    print(max(max(tomato)) - 1)

ldh5730 4년 전 1

from collections import deque

next_pos = deque()

x,y = next_pos.popleft()

list.pop(0)은 시간복잡도가 O(N)입니다. 시간복잡도가 O(1)인 deque.popleft()를 사용하세요

이외에도 python으로 문제 풀 때 중요한 부분을 살펴보시길 바랍니다.

https://www.acmicpc.net/blog/view/70

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())

tomato = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]

q_cnt = 0
next_pos = deque()

for i in range(m):
    for j in range(n):
        if tomato[i][j] == 1:
            q_cnt = q_cnt + 1
            next_pos.append((i, j))

s_cnt = 0
while next_pos:
    x, y = next_pos.popleft()
    value = tomato[x][y]

    s_cnt = s_cnt + 1
    for i in range(4):
        temp_x = x + dx[i]
        temp_y = y + dy[i]

        if 0 <= temp_x < m and 0 <= temp_y < n :
            if not tomato[temp_x][temp_y] :
                tomato[temp_x][temp_y] = value + 1
                next_pos.append((temp_x, temp_y))

flag = False

for x in tomato:
    if 0 in x:
        flag = True
        break

if q_cnt == s_cnt:
    print(0)
elif flag:
    print(-1)
else:
    print(max(max(tomato)) - 1)

bsy3719 4년 전 0

감사합니다 ㅠㅠ list.pop이 O(n)인줄은 정말 몰랐네요

bsy3719 4년 전 0

궁금한게 있는데 sys로 input 받는거랑 input()으로 받는거랑 차이가 있나요??

ldh5730 4년 전 0

sys.stdin.readline()과 input()차이를 말씀하시는 건가요?

sys.stdin.readline()이 속도가 더 빨라서, input()대신 사용하고 있습니다. 백준 문제 풀때도 input()으로 풀면 시간초과가 나온다는 경우를 본 것 같은데, 어디서 찾을 수 있는지 모르겠네요

그리고 sys.stdin.readline()은 받으면 끝에 \n이 붙어있고 input()은 없는 걸로 알고 있습니다.

bsy3719 4년 전 1

친절한 답변감사합니다.

많이배워가요 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[python3] 시간초과문제 ㅠㅠㅠ

bsy3719 4년 전 0

ldh5730 4년 전 1

bsy3719 4년 전 0

bsy3719 4년 전 0

ldh5730 4년 전 0

bsy3719 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말