백준 2014번 부분 배열 고르기에서 stkang9409님의 풀이를 보고 정리한 글이다.
솔직히 아직 제대로 설명을 못하겠다. 마스터하지 못한 것이다. 현재까지 머릿 속에 정리된 내용과 코드를 남겨 놓는다.
히스토그램
백준 1725번 히스토그램 문제가 더 기본적인 형태이다.
array[i:j]의 히스토그램에서 만들 수 있는 최대 넓이의 직사각형은 min(array[i:j) * (j - i)이다.
결론적으로 array를 반복문으로 돌면서, 감소하지 않는 형태로 stk을 만들며
stk의 top을 왼쪽끝(i에 해당하는 막대) 현재 인덱스를 오른쪽 끝(j)으로 하는 직사각형의 넓이를 구해나간다.
과정을 자세히 설명하면,
stk에 들어가는 포맷은 (막대의 높이(height), 인덱스(i: 직사각형의 왼쪽끝))이다.
array를 돌면서 현재의 막대의 높이가 stk의 top보다 같거나 큰 경우에만 stk에 push한다.
- 즉, 스택을 감소하지 않은 형태로 막대를 push한다는 것이고,
- 이는 k = 0, 1, ... , len(stk) - 2 에 대해서 막대 stk[k]는 막대 stk[k + 1] 보다 같거나 작다는 것을 보장한다.
- 연쇄적으로 생각하면 막대 stk[k]의 높이를 사용하며 막대 stk[k]를 직사각형의 왼쪽끝으로 하고 stk의 top을 직사각형의 오른쪽 끝으로 하는 직사각형을 만드는 것을 보장한다. stk의 모든 막대에 대해서 말이다.
- top의 오른쪽 끝(j)이란 array를 돌면서 top보다 작은 막대를 만났을 때, 그 때의 인덱스로 정의하면 문제가 위의 논리를 거스르지 않으며 적절한 선택이 된다.
from sys import stdin
input = stdin.readline
def solution(N, array):
# 빈 튜플 ()은 대소 비교시 어떠한 튜플보다도 작다.
# stk이 비게 하지 않는 역할을 해주어 아래 while문에서 반복문마다 stk이 있는지 점검할 필요가 없다.
stk = [()]
answer = 0
for j, height in enumerate(array):
i = j
# 반복문을 돌면서 인덱스는 증가하므로 height로만 비교해도 된다. 하지만 stk에 빈 tuple를 기저에 마련했기 때문에, tuple로 비교한다.
while (height, j) < stk[-1]:
h, i = stk.pop()
answer = max(answer, (j - i) * h)
stk.append((height, i))
return answer
if __name__ == '__main__':
N = int(input())
# [0]을 마지막에 추가하는 이유는, array를 모두 다 돌고 났을때 stk에 남아있는 모든
array = [int(input()) for _ in range(N)] + [0]
print(solution(N, array))
# 빈 튜플 ()은 대소 비교시 어떠한 튜플보다도 작다. stk이 비게 하지 않는 역할을 해주어 아래 while문에서 반복문마다 stk이 있는지 점검할 필요가 없다.
인덱스 조작하기
단순히 직사각형의 가로길이를 구했던 위의 문제와 다르게 막대들의 높이의 합에다가 최소 막대 높이를 곱하게 된다. 높이들의 합을 인덱스라고 생각하고 풀면 위의 문제와 비슷하다. eumerate(list)를 상용하지 않고 직접 넓이의 합을 인덱스로 정의하는게 포인트다.
def solution(N, A):
stk = [()]
answer = 0
j = 0
for height in A:
i = j
while (height, j) < stk[-1]:
h, i = stk.pop()
answer = max(answer, (j - i) * h)
stk.append((height, i))
j += height
return answer
if __name__ == "__main__":
N = int(input())
A = list(map(int, input().split() + [0]))
print(solution(N, A))