글 읽기 - python 스택이용했는데 시간초과가 납니다.

wkdalstjd101 4년 전 0

스택을 이용하여 풀었는데 시간초과가 발생합니다.

pypy로 제출해도 시간초과가 나는걸로보여 python문제는 아닌것같습니다.

고수님들의 도움 부탁드립니다 ㅠ

import sys
import collections
def histo(A):
    N=len(A)
    result=[0 for _ in range(N)]
    stk=collections.deque()
    stk.append(0)
    result[0]=A[0]
    #result 초기값(세로로 긴 직사각형과 가로로 긴 직사각형중 넓은거)
    for n in range(1,N):
        result[n]=max(A[n],(n+1)*min(A[:n]))
    #탑이 더 크거나 같으면 pop
    for i in range(1,N):
        while stk and A[stk[0]]>=A[i]:
            stk.popleft()
        #top보다 작으면 push
        if stk:
            if A[stk[0]]<A[i]:
                stk.appendleft(i)
        elif not stk:
            if A[i-1]<A[i]:
                stk.appendleft(i)
        #스택에 쌓인 값으로 넓이 계산
        for j in stk:
                result[i]=max(result[i],(i-j+1)*A[j])
    return max(result)

N,*A=map(int,sys.stdin.readline().rstrip().split())
while N!=0:
    print(histo(A)) 
    N,*A=map(int,sys.stdin.readline().rstrip().split())

sait2000 4년 전 0

24~25번 줄이 문제 같습니다. 1부터 100000까지 증가하는 순서대로 직사각형이 있으면 어떻게 될까요.

wkdalstjd101 4년 전 0

@sait2000

하지만 언급해주신 경우에 직접 연산을 해보지않고 비교해볼수있는 방법이있나요....??

핵심 아이디어는 뽑을 때만 계산하는 겁니다. 왜냐하면 어떤 막대 기준으로 자기 주위에 크거나 같은 막대를 다 포함하게 골라야 최대가 될 텐데 그러면 자기보다 작은 게 나와서 자기가 팝 되는 순간까지 골라야 하니까요. 구체적으로 뭘 언제 어떻게 계산해야 하는지는 제가 설명할 자신이 없고 구글 같은 데 백준 6549 이런 식으로 검색하면 블로그 글 같은 거 나오자 않을까요

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

문제

문제

출처

ICPC

python 스택이용했는데 시간초과가 납니다.

wkdalstjd101 4년 전 0

sait2000 4년 전 0

wkdalstjd101 4년 전 0

sait2000 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말