[Python] 백준, 1725(스택)

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

1725번: 히스토그램

지난번에 풀이한 히스토그램 문항이랑 같다. 근데 지난번 풀이때 놓친 부분이 있어서 간단히 소개하려한다.

# PYTHON CODE

        n = int(input()) 
      

        s1 = [int(input()) for _ in range(n)] 
      

        s2 = [0] 
      

        answer = 0 
      

        s1.insert(0, 0) 
      

        s1.append(0) 
      

          
      
 for i in range(1, n + 2): 
      

            while s2 and s1[s2[-1]] > s1[i]: 
      

                k = s2.pop() 
      

                answer = max(answer, (i - s2[-1] - 1) * s1[k]) 
      

            s2.append(i) 
      

          
      
 print(answer) 
      

* line3 : 너비 계산시 s2[-1]을 불러올 경우 IndexError를 방지함.
* line5 : 가장 작은 높이인 0을 배치해서 알고리즘에는 지장을 주지 않으며 s2[0]과 조화를 맞추어 index를 깔끔히 함.
* line6 : s2에 처리되지 않고 남아있는 인덱스들을 정리 가능하게 해줌.