[백준(BOJ)] 6549번 : 히스토그램에서 가장 큰 직사각형 - PYTHON[파이썬]

https://www.acmicpc.net/problem/6549

6549번: 히스토그램에서 가장 큰 직사각형

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 자료 구조
• 세그먼트 트리
• 분할 정복
• 스택

 

---

 

⊙ 문제 접근 과정

 

왼쪽부터 차례대로 검색해준다.

 

스택에 최솟값을 넣어주고 그 값이랑 비교했을 때, pop을 하며 최댓값을 찾아가면 된다.

 

고민하다가 코드로 구현이 힘들어 인터넷을 활용한 문제다.

 

---

 

⊙ 문제 풀이

 

from collections import deque
import sys

while True:
    rec = list(map(int, sys.stdin.readline().split()))
    N = rec.pop(0)

    if N == 0:
        break

    stack = deque()
    answer = 0

    for i in range(N):
        while len(stack) != 0 and rec[stack[-1]] > rec[i]:
            tmp = stack.pop()

            if len(stack) == 0:
                width = i
            else:
                width = i - stack[-1] - 1
            answer = max(answer, width * rec[tmp])
        stack.append(i)

    while len(stack) != 0:
        tmp = stack.pop()

        if len(stack) == 0:
            width = N
        else:
            width = N - stack[-1] - 1
        answer = max(answer, width * rec[tmp])

    print(answer)

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

플래티넘 잘 풀고 싶다

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!