백준 - 6549 히스토그램에서 가장 큰 직사각형 풀이

문제

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

스택 사용 방법

풀이

답

kotlin code

fun main() {
    val inputList = mutableListOf<IntArray>()
    while (true)
    {
        val line = readln().trim()
        if(line == "0") break
        if(line.isEmpty()) continue
        inputList.add(line.split(" ").drop(1).map { it.toInt() }.toIntArray())
    }

    for(histogram in inputList) {
        println(getMaxArea(histogram))
    }
}

fun getMaxArea(histogram: IntArray): Long {
    val stack = java.util.Stack<Int>()
    var max = 0L
    for((index, curHeight) in histogram.withIndex()) {
        max = getMaxArea(index, max, stack, histogram, curHeight)
        stack.push(index)
    }
    while(stack.isNotEmpty()) {
        max = getMaxArea(histogram.size, max, stack, histogram)
    }
    return max
}

private fun getMaxArea(index: Int, curMax: Long, stack: java.util.Stack<Int>, histogram: IntArray, curHeight: Int = -1): Long {
    var max = curMax
    while (stack.isNotEmpty() && curHeight <= histogram[stack.peek()]) {
        val height = histogram[stack.pop()].toLong()
        val width = (index - stack.peekOrDefault() - 1)
        max = kotlin.math.max(max, height * width)
    }
    return max
}

fun java.util.Stack<Int>.peekOrDefault(defaultValue: Int = -1): Int = when {
    empty() -> defaultValue
    else -> this.peek()
}

분할 정복법

풀이

답

kotlin code

fun main() {
    val inputList = mutableListOf<IntArray>()
    while (true)
    {
        val line = readln().trim()
        if(line == "0") break
        if(line.isEmpty()) continue
        inputList.add(line.split(" ").drop(1).map { it.toInt() }.toIntArray())
    }

    for(histogram in inputList) {
        println(getMaxArea(0, histogram.size, histogram))
    }
}

fun getMaxArea(fromIndex: Int, toIndex: Int, histogram: IntArray): Long = when(fromIndex) {
    toIndex - 1 -> histogram[fromIndex].toLong()
    else -> {
        val midIndex = (fromIndex + toIndex) / 2
        val leftMaxArea = getMaxArea(fromIndex, midIndex, histogram)
        val rightMaxArea = getMaxArea(midIndex, toIndex, histogram)
        val midMaxArea = getMidMaxArea(fromIndex, toIndex, midIndex, histogram)
        kotlin.math.max(kotlin.math.max(leftMaxArea, rightMaxArea), midMaxArea)
    }

}

fun getMidMaxArea(fromIndex: Int, toIndex: Int, midIndex: Int, histogram: IntArray): Long {
    var leftIndex = midIndex
    var rightIndex = midIndex
    val lastIndex = toIndex - 1

    var height = histogram[midIndex].toLong()
    var maxArea = height


    while (fromIndex < leftIndex && rightIndex < lastIndex) {
        if(height == 0L || maxArea > (toIndex - fromIndex) * height) return maxArea
        val curHeight =
            if (histogram[leftIndex - 1] >= histogram[rightIndex + 1]) histogram[--leftIndex].toLong()
            else histogram[++rightIndex].toLong()
        if (curHeight < height) height = curHeight
        val width = rightIndex - leftIndex + 1
        val area = height * width
        if (area > maxArea) maxArea = area
    }

    while (fromIndex < leftIndex) {
        if(height == 0L || maxArea > (toIndex - fromIndex) * height) return maxArea
        val curHeight = histogram[--leftIndex].toLong()
        if (curHeight < height) height = curHeight
        val width = rightIndex - leftIndex + 1
        val area = height * width
        if (area > maxArea) maxArea = area
    }

    while (rightIndex < lastIndex) {
        if(height == 0L || maxArea > (toIndex - fromIndex) * height) return maxArea
        val curHeight = histogram[++rightIndex].toLong()
        if (curHeight < height) height = curHeight
        val width = rightIndex - leftIndex + 1
        val area = height * width
        if (area > maxArea) maxArea = area
    }
    return maxArea
}

Segment Tree + 분할 정복법

풀이

답

kotlin code

fun main() {
    val inputList = mutableListOf<IntArray>()
    while (true)
    {
        val line = readln().trim()
        if(line == "0") break
        if(line.isEmpty()) continue
        inputList.add(line.split(" ").drop(1).map { it.toInt() }.toIntArray())
    }

    for(histogram in inputList) {
        println(getMaxArea(histogram))
    }
}

fun getMaxArea(histogram: IntArray): Long {
    val segmentTree = getSegmentTree(histogram)

    return getMaxArea(0, histogram.size, segmentTree, histogram)
}

fun getMaxArea(startIndex: Int, endIndex: Int, segmentTree: IntArray, histogram: IntArray): Long = when {
    startIndex == endIndex - 1 -> histogram[startIndex].toLong() * (endIndex - startIndex)
    startIndex >= endIndex -> 0L
    else -> {
        val minIndex = getMinIndex(0, 0, histogram.size, startIndex, endIndex, segmentTree, histogram)
        val leftArea = getMaxArea(startIndex, minIndex, segmentTree, histogram)
        val rightArea = getMaxArea(minIndex + 1, endIndex, segmentTree, histogram)
        val thisArea = histogram[minIndex].toLong() * (endIndex - startIndex)
        kotlin.math.max(kotlin.math.max(leftArea, rightArea), thisArea)
    }
}

fun Int.getLeftNode() = this * 2 + 1

fun Int.getRightNode() = this * 2 + 2

fun getMinIndex(node: Int, histogramFromIndex: Int, histogramToIndex: Int, targetFromIndex: Int, targetToIndex: Int, segmentTree: IntArray, histogram: IntArray): Int {
    if(targetToIndex <= histogramFromIndex || histogramToIndex <= targetFromIndex) return -1
    if(histogramFromIndex >= targetFromIndex && targetToIndex >= histogramToIndex) return segmentTree[node]

    val histogramMidIndex = kotlin.math.ceil((histogramFromIndex + histogramToIndex) / 2.0).toInt()
    val leftIndex = getMinIndex(
        node.getLeftNode(),
        histogramFromIndex,
        histogramMidIndex,
        targetFromIndex,
        targetToIndex,
        segmentTree,
        histogram
    )
    val rightIndex = getMinIndex(
        node.getRightNode(),
        histogramMidIndex,
        histogramToIndex,
        targetFromIndex,
        targetToIndex,
        segmentTree,
        histogram
    )

    if(leftIndex == -1) return rightIndex
    if(rightIndex == -1) return leftIndex
    return if(histogram[leftIndex] <= histogram[rightIndex]) leftIndex else  rightIndex
}

private fun getSegmentTree(histogram: IntArray): IntArray {
    val segmentTree = IntArray(histogram.getTreeSize()) { -1 }
    initTree(0, 0, histogram.size, segmentTree, histogram)
    return segmentTree
}

private fun initTree(node: Int, startIndex: Int, endIndex: Int, segmentTree: IntArray, histogram: IntArray): Int = when (startIndex) {
    endIndex - 1 -> {
        segmentTree[node] = startIndex
        segmentTree[node]
    }
    else -> {
        val midIndex = getTreeMidIndex(startIndex, endIndex)
        val left = initTree(node.getLeftNode(), startIndex, midIndex, segmentTree, histogram)
        val right = initTree(node.getRightNode(), midIndex, endIndex, segmentTree, histogram)
        segmentTree[node] = if(histogram[left] <= histogram[right]) left else right
        segmentTree[node]
    }
}

private fun IntArray.getTreeSize() = Math.pow(2.0, kotlin.math.ceil(kotlin.math.log2(this.size.toDouble()))).toInt() * 2 - 1

private fun getTreeMidIndex(startIndex: Int, endIndex: Int) = kotlin.math.ceil((startIndex + endIndex) / 2.0).toInt()

Attachments

• 이미지 원본