글 읽기 - [파이썬] 시간 초과 이유 ㅜㅜ

mike1201 5년 전 0

pypy3으로 하면 되는데 python3로 하면 시간초과가 나서 질문드립니다ㅜㅜ

시간 초과가 나지 않은 다른 분들의 코드를 보면 논리가 별반 다를바가 없는데 왜 시간초과가 나는지 모르겠습니다....@

import sys
from sys import stdin
from collections import deque
ls = list(map(int, stdin.readline().strip().split(' ')))
R = ls[0]; C = ls[1]
first_row = str(stdin.readline().strip())
first_letter = first_row[0]
graph = []
graph.append(first_letter*(C+2))
graph.append(first_letter+ first_row+first_letter)

for i in range(R-1):
    row = str(stdin.readline().strip())
    row = first_letter + row + first_letter
    graph.append(row)
graph.append(first_letter*(C+2))

def dfs(R, C, graph):
    stack = deque([ (1,1) ]) # 고려할 위치
    start_letter = graph[1][1]
    stack_letter = deque([start_letter]) # 방문했던 알파벳
    dr = [-1,1,0,0]
    dc = [0,0,-1,1]
    max_count = [1]
    while stack:
        r, c = stack.pop()
        tmp_letter = stack_letter.pop()
        count_2 = 0
        for i in range(4):
            rs = r + dr[i]
            cs = c + dc[i]
            if graph[rs][cs] in tmp_letter: # 방문했던 알파벳이라면
                count_2 = count_2 + 1
            else: # 방문하지 않았다면
                stack.append((rs,cs))

                stack_letter.append( graph[rs][cs] + tmp_letter )

        if count_2 == 4: # 어디에도 못간다면
            max_count.append( len(tmp_letter) )
    print(max(max_count))


dfs(R, C, graph)

djm03178 5년 전 0

Python이 그만큼 느린 언어이기 때문입니다. C나 C++에 비해서 수십 배에서 최대 100배까지 느린 언어라고 할 수 있기 때문에, 이 문제에서는 웬만큼 최적화를 잘 해서는 통과하기 어렵습니다. PyPy는 속도 면에서는 Python에 비해서는 매우 개선이 된 언어입니다.

mike1201 5년 전 0

@djm03178 그렇군요... 그러면 코테 대비를 한다면 pypy3을 기준으로 판단해도 될까요?

djm03178 5년 전 0

코딩 테스트에서 PyPy3를 지원한다면 쓰시면 되고, 아니라면 사실 좀 애매하긴 합니다. 파이썬이라는 언어가 원체 느리기 때문에 테스트에서 이 문제는 Python으로도 충분히 풀 수 있다는 걸 보장해줄지는 모릅니다.

그래서 시험 대비용이라면 사실 파이썬 계열의 언어는 그다지 추천할만하지 못하고, C/C++이나 Java를 쓰는 것이 더 안전하다고 할 수 있습니다.

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

문제

문제

출처

ICPC

[파이썬] 시간 초과 이유 ㅜㅜ

mike1201 5년 전 0

djm03178 5년 전 0

mike1201 5년 전 0

djm03178 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말