백준 6549 히스토그램에서 가장 큰 직사각형 Kotlin (스택)

문제 출처 : 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이 하나 주어진다.

출력

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

알고리즘 분류

• 자료 구조
• 세그먼트 트리
• 분할 정복
• 스택

풀이

2021.08.26 - [알고리즘 문제 풀이/백준] - 백준 1726 히스토그램 Kotlin (스택)

이전에 포스팅한 1726번 문제와 동일하니 위의 글에서 풀이를 참조하면 된다.

코드

import java.util.*
import kotlin.math.*
fun main()=with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    while(true){
        val tk = StringTokenizer(br.readLine())
        val n = Integer.parseInt(tk.nextToken())
        if(n==0){
            break
        }
        val stack = Stack<Int>()
        val high = LongArray(n+2)
        var answer = 0L
        var num : Long
        stack.push(0)

        for(i in 1 .. n+1){
            if(i==n+1){
                num = 0
            }
            else {
                num = tk.nextToken().toLong()
            }
            high[i]=num
            while(stack.isNotEmpty() && high[stack.peek()]>num){
                val highIdx = stack.pop()
                answer = max(answer, high[highIdx]*(i-stack.peek()-1))
            }
            stack.push(i)
        }
        write("$answer\n")
    }
    close()
}