[BOJ/Kotlin]히스토그램에서 가장 큰 직사각형

문제

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

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

입력

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

출력

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

풀이(Kotlin)

import java.util.*
import kotlin.math.*

// 백준: 6549 - 히스토그램에서 가장 큰 직사각형
fun main() = with(System.out.bufferedWriter()) {
    val br = System.`in`.bufferedReader()
    
    while(true) {
        val st = StringTokenizer(br.readLine())    // 한 줄 입력
        val n = Integer.parseInt(st.nextToken())   // 직사각형 수
        if(n == 0) break                           // 0 입력 시 종료
        
        val stack = Stack<Int>()             // 히스토그램의 인덱스를 저장하는 스택
        val height = LongArray(1 + n + 1)    // 앞뒤에 높이가 0인 히스토그램 추가
                                             // (점점 높이가 커지는/작아지는 히스토그램을 대비)
        var result = 0L                      // 출력값
        var nextHight: Long                  // 다음 히스토그램의 높이
        stack.push(0)    // 맨 앞을 높이가 0인 히스토그램으로 채움

        for(idx in 1..n + 1) {
            if(idx == n + 1) nextHight = 0    // 맨 뒤을 높이가 0인 히스토그램으로 채움
            else nextHight = st.nextToken().toLong()    // 다음 히스토그램의 높이
            height[idx] = nextHight    // 히스토그램 높이 배열에 저장
            // 현재 히스토그램의 높이보다 다음 히스토그램의 높이가 작을 때까지 반복
            // (현재 히스토그램 높이보다 큰 높이가 나올 때까지 스택에 현재 히스토그램 인덱스 푸시)
            // (=> 현재보다 다음 히스토그램의 높이가 작으면, 현재까지 지나온 히스토그램의 넓이가
            // 가장 넓다는 의미)
            while(stack.isNotEmpty() && height[stack.peek()] > nextHight) {
                val hightIdx = stack.pop()    // 현재까지의 히스토그램의 인덱스
                // 결과 = max(이전 결과값, 높이 x 밑변)
                // => 현재까지 지나온 히스토그램 높이 x 현재 인덱스에서 지나온 히스토그램까지의 길이(밑변))
                result = max(result, height[hightIdx] * (idx - stack.peek() - 1))
            }
            stack.push(idx)
        }
        // 출력
        write("$result\n")
    }
    close()
}

 

참고

https://ongveloper.tistory.com/207

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

https://st-lab.tistory.com/255

[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 - JAVA [자바]

 

---

다시 알고리즘 공부 시작...^^

언어 고민하다가 코틀린 언어 자주 쓸 거 같고

문법도 더 배워보고자 선택함

근데 자바랑 같이 풀어봐도 될듯!?

 

근데 이 문제 어케 스택으로 풀 생각을 하신 거임??

(스택으로 푸는 유명한 문제라고 한다....)

이해가안가네

아니 풀이 과정은 이해가 됐다고 쳐(당연함 하나하나 그려봄)

근데 그 과정을 생각하기까지의... 접근 과정을 모르겠네

천재들인가봐