흙금이네 블로그

아이디어 스택을 이용하여 각 위치에서 해당 직사각형의 높이로 만들 수 있는 가장 큰 직사각형 넓이를 구해 나간다. 풀이 6549번 히스토그램에서 가장 큰 직사각형에서 스택을 이용한 풀이 #2와 같다. 첫 번째 수는 N, 직사각형의 높이들은 sys.stdin.readlines로 H에 입력 받고, H 끝에는 0을 추가한다. 직사각형의 넓이를 구하기 위해 필요한 직사각형의 위치들을 스택 stack에 저장하고, 이 위치로 직사각형 양쪽 끝과 H에서 해당 직사각형의 높이를 알 수 있어 각 위치에서의 직사각형의 면적을 구할 수 있다. for문에서는 차례로 직사각형 높이가 증가하면 그 위치를 스택에 넣고 감소하면 스택에서 위치를 꺼내 그 넓이를 계산한다. 위치 i의 직사각형 높이가 stack[-1] 위치의 직사각형 ..