글 읽기 - 백준 님이 게시판으로 알려주신 스택을 활용하여 문제에 도전했는데 실패했습니다.

alsrl9 3년 전 0

스택을 활용하여 해결하는 방법을 python으로 구현했습니다.

로직 자체에 대한 이해가 부족해서 깔끔하게 설명을 못 드리는 점 죄송합니다.

게시판의 모든 반례를 시험해봤는데 어디가 문제인지 찾지 못했습니다.

어떤 점이 문제가 되는지 알려주실 수 있으실까요?

import sys

while True:
    S = list(map(int, sys.stdin.readline().split()))
    if S[0] == 0:
        break

    answer = 0
    stack = []
    for i in range(1, len(S)):
        right = i-1
        while len(stack) > 0 and S[stack[len(stack)-1]] > S[i]:
            temp = stack.pop()
            left = temp if len(stack) == 0 else stack[len(stack)-1] + 1
            answer = max(answer, S[temp] * (right - left + 1))
        stack.append(i)
    
    right = len(S)-1
    while len(stack) > 0:
        temp = stack.pop()
        left = 1 if len(stack) == 0 else stack[len(stack)-1] + 1
        answer = max(answer, S[temp] * (right - left + 1))
    
    print(answer)

alsrl9 3년 전 0

해결했습니다.

14번 라인에서 stack이 비어있을 때 left를 temp로 정해준 부분이 잘못됐습니다.

밑에서는 left의 기본값을 1로 정해두고 위에서는 왜 저렇게 작성했는지 지금 생각하면 의문이네요.

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

문제

문제

출처

ICPC

백준 님이 게시판으로 알려주신 스택을 활용하여 문제에 도전했는데 실패했습니다.

alsrl9 3년 전 0

alsrl9 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말