백준 6549_Python

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

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

 

문제

---

히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 같은 너비를 가지고 있지만, 높이는 서로 다를 수도 있다. 예를 들어, 왼쪽 그림은 높이가 2, 1, 4, 5, 1, 3, 3이고 너비가 1인 직사각형으로 이루어진 히스토그램이다.

히스토그램에서 가장 넓이가 큰 직사각형을 구하는 프로그램을 작성하시오.

 

 

입력

---

입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ 1,000,000,000)가 주어진다. 이 숫자들은 히스토그램에 있는 직사각형의 높이이며, 왼쪽부터 오른쪽까지 순서대로 주어진다. 모든 직사각형의 너비는 1이고, 입력의 마지막 줄에는 0이 하나 주어진다

 

 

출력

---

각 테스트 케이스에 대해서, 히스토그램에서 가장 넓이가 큰 직사각형의 넓이를 출력한다.

 

 

 

접근법

---

1.  Stack 을 이용한 문제 이며, stack 시에 우선 s[] 는 순번을 저장하는  list 그리고, ans 는 정답을 체킹하는 integer이다.
2.  n 과 l 을 입력 받아 , ㅣ의 수가 stack에 추가시켜 주는데, 이때 , stack 보다 작은 l[i]가 들어올시에, stack 에 있는 수는 더 이상, 오른쪽으로 진행이 불가( stack[s.pop()]의 오른쪽은 자기 자신보다 작으므로, 진행이 불가능하다.) 하므로, 여기서 stack.pop() 을 시켜주고 ans 을 갱신시켜준다.

추가로 append(0)을 시켜주었는데, 다른 분의 풀이를 참고하였다..(아이디어 정말 대단함.)

- 0을 추가시켜주면, for 문의 i 가 l의 끝부분에 도달하였을시에 0이 모든 직사각형보다 작으므로, 따로 전처리(i가 끝부분에 도달하면, stack 을 비워주는 코드를 또 작성해야함.)를 할 필요없이 자동으로 진행이 되기 때문에 정말 좋은 아이디어인듯 싶다.

 

while True:
    n, *l = list(map(int,input().split()))
    # s 는 번호를 담을 stack 이다.
    # n 이 0 일때는 break 문을 통해 빠져나가준다.
    if n == 0: break
    s = []
    # ans 는 최종적으로 가장 큰 직사각형의 넓이를 나타낸다.
    ans = 0
    # 0을 더해주는 이유는 append 해주지 않으면, for 문에서 끝까지 왔을때의 처리를 한번 더 해줘야
    # 하지만, 여기서 0 을 추가해줌으로써 자동적으로, 넓이 처리가 되게끔 하였음.
    l.append(0)
    for i,h in enumerate(l):
        while s and l[s[-1]]>h:
            #높이를 결정하는 height 는 l[i] 그전의 것이 되게 된다.
            height = l[s.pop()]
            if s : 
                width = i-s[-1]-1
            else:
                width = i
            ans = max(ans,height*width)
        s.append(i)
    print(ans)