풀이
import sys;
while True:
N, *info = map(int, sys.stdin.readline().strip().split())
if N == 0:
break
info.append(0)
S = []
rst = 0
for i in range(N+1):
# 스택에 높이와 인덱스를 저장할건데 pointer는 인덱스를 가리킴
# 이때 저장하는 인덱스는 단순히 그 높이의 인덱스가 아니라 현재 높이로 만들수 있는 전의 인덱스를 가르킴
pointer = i
# 현재 높이가 스택에 마지막 요소의 높이보다 작으면 rst값을 갱신
while S and info[i] < S[-1][0]:
h, d = S.pop()
# 이때 포인터를 d로 가르키게함 자세한 설명은 후기에..
pointer = d
tmp = h * (i-d)
rst = max(rst, tmp)
S.append((info[i], pointer))
print(rst)
후기
- 플레인데 쉬워보여서 도전한 문제
- 처음엔 단순히 2중 for문 돌려서 구할 수는 있었지만, 시간 초과가 남
- for문 안에 for문이 아닌 while문을 돌려서 조건을 비교할 수 있는지 연산을 줄여줌
- 근데 첫 풀이는 틀렸다는 채점결과가 계속 나옴
- 이유는 처음엔 S에 (info[i], i)로 넣어주어서 3 2 3 4 5 1 이런 경우에 높이가 2인 경우 스택에 (2, 1)을 넣어줬는데,
- (2, 0)을 넣어줬어야함 그래서 pointer라는 변수를 추가해서 인덱스를 바꿔 스택에 저장
