[백준] 1725번 : 히스토그램 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 이전의 6549번 : 히스토그램에서 가장 큰 직사각형 문제와 유사한 문제이다.

하지만 이전 6549번 문제와 다른 점은 시간 제한이 1초에서 0.7초로 줄었다는 점이다.

시간 제한이 줄었기 때문에 6549번 문제를 풀었을 때처럼 해결하면 시간초과가 발생할 수 있다.

시간을 줄이기 위해 반복문이 최대한 적게 실행되도록 수정해보려고 했다.

하여 이전 6549번 코드의 for 문 안 while 반복문이 최소한으로 실행되도록 수정했다.

 

스택 자료구조를 그대로 사용하고 막대의 위치를 한 번씩만 가져와서 스택 자료구조에 막대가 있고 마지막으로 저장된 막대의 높이가 현재 지정하고 있는 막대의 높이보다 크면 막대를 제거하며 가장 큰 직사각형의 넓이를 구한다.

현재 지정하고 있는 막대의 위치와 직사각형의 넓이를 구할 때 지정하는 막대의 위치를 구별하기 위해 변수를 2개 사용하였다. (이 부분이 가장 이해하기 어려운 부분인 것 같다.)

현재 지정한 막대의 높이가 작으면 이전까지 저장되어 있던 막대를 하나씩 가져와 가져온 막대의 높이를 가지는 가장 큰 직사각형의 넓이를 구한다.

매번 직사각형의 넓이를 구하면 이전까지 저장되었던 가장 큰 직사각형 넓이와 비교하여 더 큰 값을 저장한다.

스택에 자료를 추가할 때는 위치와 막대의 높이를 리스트로 묶어 추가한다.

 

모든 막대를 가져와 직사각형의 넓이를 구한 뒤, 스택에 남아있는 막대들도 사용하여 가장 큰 직사각형 넓이를 구한 뒤 이전 값과 비교하여 큰 값을 저장한다.

이는 모든 막대가 동일한 높이로 주어졌을 경우를 고려한 것으로 전체 재탐색 후 가장 큰 직사각형 넓이를 구해야 한다.

 

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 가로 칸의 수를 입력받는다. N = int(sys.stdin.readline())
3. 각 막대의 높이를 저장할 리스트를 생성하고 hist = list()
4. 가로 칸의 수만큼 높이를 입력받아 리스트에 추가한다. for _ in range(N): hist.append(int(sys.stdin.readline()))
5. 스택 자료구조를 활용한다. stack = list()
6. 최종 정답인 가장 큰 직사각형의 넓이를 저장할 변수를 생성하고 초기화한다. answer = 0
7. 각 막대의 위치를 하나씩 불러오며 for i in range(N)
   1. 현재 막대의 위치를 따로 저장한다. idx = i
   2. 스택 자료구조가 비어있지 않거나 마지막으로 저장되어 있는 막대의 높이가 현재 막대의 높이보다 크다면 while (stack and stack[-1][1] > hist[i])
      1. 마지막으로 저장되어 있던 막대를 스택 자료구조에서 제거하고 막대의 위치와 높이를 가져온다. idx, height = stack.pop()
      2. 현재 막대의 위치에서 가져온 막대의 위치를 뺀 값(밑변 길이)에 가져온 막대의 높이를 곱하여 값을 저장한다. rst = (i - idx) * height
      3. 새롭게 구한 직사각형의 넓이와 기존에 저장되어 있던 직사각형의 넓이 중 더 큰 값을 정답 변수에 저장한다. answer = max(answer, rst)
   3. 막대의 위치와 현재 막대의 높이를 리스트로 묶어 스택 자료구조에 추가한다. stack.append([idx, hist[i]])
8. 모든 막대를 가져와 가장 큰 직사각형의 넓이를 구했다면 이후 스택 자료구조에 저장되어 있는 막대들도 살펴봐야 한다. 스택 자료구조가 비기 전까지 반복하며 while (stack)
   1. 마지막으로 저장되어 있던 막대를 스택 자료구조에서 제거하고 막대의 위치와 높이를 가져와 idx, height = stack.pop()
   2. 마지막 막대의 위치에서부터 가져온 막대의 위치를 빼고(밑변 길이) 그 값에 가져온 막대의 높이를 곱해  rst = (N - idx) * height
   3. 새롭게 구한 직사각형의 넓이와 기존에 저장되어 있던 직사각형의 넓이 중 더 큰 값을 정답 변수에 저장한다. answer = max(answer, rst)
9. 최종적으로 구한 가장 큰 직사각형의 넓이를 출력한다. print(answer)

728x90

3. 소스코드

import sys

N = int(sys.stdin.readline())
hist = list()
for _ in range(N):
    hist.append(int(sys.stdin.readline()))

stack = list()
answer = 0
for i in range(N):
    idx = i
    while (stack and stack[-1][1] > hist[i]):
        idx, height = stack.pop()
        rst = (i - idx) * height
        answer = max(answer, rst)

    stack.append([idx, hist[i]])
    
while (stack):
    idx, height = stack.pop()
    rst = (N - idx) * height
    answer = max(answer, rst)

print(answer)