글 읽기 - 시간초과 질문입니다 (파이썬)

rkdr055 6년 전 0

코드 두개의 경우로 짜봤는데요

위의 코드는 시간초과인데 아래의 코드는 맞습니다 가 출력됩니다

둘의 차이점이라고는 문자열을 입력하는 방법과 반복문을 돌리는 방법 뿐인데 왜 차이가 나는걸까요?

lambda 를 이용해서 문자열을 입력받는것이 len를 사용하는 것에 시간영향을 미치나요?

코드1
import sys
a=sys.stdin.readline()
list1=[]
count=0
for i in range(len(a)):
    if a[i]=="(":
        list1.append(i)
    elif a[i]==")":
        if i-max(list1)==1:
            list1.pop()
            count+=len(list1)
        else:
            count+=1
            list1.pop()
print(count)

코드2
import sys
z= lambda: sys.stdin.readline().strip()
a=z()
list1=[]
count=0
for (i,a) in enumerate(a):
    if a=="(":
        list1.append(i)
    elif a==")":
        if i-max(list1)==1:
            list1.pop()
            count+=len(list1)
        else:
            count+=1
            list1.pop()
print(count)

jh05013 6년 전 0

아래 코드가 맞으면 안 되는데요...?

max(list1)을 한 번 하는데 len(list1)만큼의 시간이 걸리므로 전체 코드는 입력 길이의 제곱만큼 시간이 걸립니다. 이 정도로는 시간 내에 길이 10만의 입력을 처리할 수 없습니다.

rkdr055 6년 전 0

질문을 잘못올렸네요 ㅎㅎ;

한 문제에 여러개 코드 만들어서 다 제출해보다 보니 헷갈렷습니다

댓글 달아주신 max(list1)을 하지말고 그냥 바로 list1[-1]을 하면 되는 문제였습니다

어차피 list1의 마지막이 제일 큰 숫자였네요.

평소에 max 써서 잘 풀다가 시간제한이 걸리니 max 문제인줄 몰랐습니다.

감사합니다.

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

문제

문제

출처

ICPC

시간초과 질문입니다 (파이썬)

rkdr055 6년 전 0

jh05013 6년 전 0

rkdr055 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말