백준 1725번 히스토그램 - SWIFT

문제

---

히스토그램에 대해서 알고 있는가? 히스토그램은 아래와 같은 막대그래프를 말한다.

 

각 칸의 간격은 일정하고, 높이는 어떤 정수로 주어진다. 위 그림의 경우 높이가 각각 2 1 4 5 1 3 3이다.

이러한 히스토그램의 내부에 가장 넓이가 큰 직사각형을 그리려고 한다. 아래 그림의 빗금 친 부분이 그 예이다. 이 직사각형의 밑변은 항상 히스토그램의 아랫변에 평행하게 그려져야 한다.

 

주어진 히스토그램에 대해, 가장 큰 직사각형의 넓이를 구하는 프로그램을 작성하시오.

 

입력

첫 행에는 N (1 ≤ N ≤ 100,000) 이 주어진다. N은 히스토그램의 가로 칸의 수이다. 다음 N 행에 걸쳐 각 칸의 높이가 왼쪽에서부터 차례대로 주어진다. 각 칸의 높이는 1,000,000,000보다 작거나 같은 자연수 또는 0이다.

 

출력

첫째 줄에 가장 큰 직사각형의 넓이를 출력한다. 이 값은 20억을 넘지 않는다.

 

문제 링크

1725번: 히스토그램

 

풀이

---

이 문제는 스택으로 푸는 방법과 세그먼트 트리로 푸는 방법 두가지가 존재한다.

세그먼트 트리로 푸는 방법은 이와 똑같은 문제인 6549번 히스토그램에서 가장 큰 직사각형에서 소개하겠다.

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

 

일정 구간의 히스토그램에서 최대 직사각형의 면적은 (가장 작은 히스토그램 높이 * 구간 수)가 된다.

작은 것을 기준으로 크기가 정해지게 된다.

이번 스택 풀이는 이를 이용한 풀이가 될 것이다.

 

 

프로그램 동작

---

가장 먼저, 높이와 스택은 이런 식의 배열로 이루어져있다.

스택에 0을 넣어줌으로 스택이 하나 들어있는 상태에서 시작한다.

스택의 값이 의미하는 바는 높이가 아닌, 높이의 인덱스이다.▼

 

 

1. 현재 높이 배열에 있는 값과 스택의 top에 있는 인덱스에 해당하는 높이 값과 비교해본다.

만약 현재 높이 배열에 있는 값이 더 크다면 스택에 해당 인덱스 값을 넣어준다.▼

 

 

2. 1번을 반복할 때, 스택의 top에 있는 인덱스에 해당하는 높이 값이 현재 높이 배열의 값보다 더 작다면, 현재 높이 배열의 값보다 더 작은 값이 나올 때 까지 pop()을 한다.

(pop()을 할 때 나온 인덱스에 해당하는 높이 값 * (현재 높이 배열 인덱스 - 스택 top값 - 1))

위의 값이 히스토그램의 면적 값이 된다.

왜 그런가하면, 1번과 2번의 내용대로 스택을 채워넣게 되면 아래 그림과 같이 스택에 증가하는 방향으로만 쌓일 것이다.

(실제 스택에는 인덱스가 들어가고, 그 인덱스에 해당하는 높이 값이 증가하는 방향으로 쌓인다는 것이다.)▼

 

 

그러다가 현재 값보다 작은 값이 들어오게 되면, 작은 값을 기준으로 히스토그램의 크기를 구할 수 밖에 없어지게 되므로, 작은 값을 push()하기 전에 값을 pop()하면서 확인해본다.▼

 

 

면적을 구할 때는 방금처럼 작은 값을 기준으로 구할 수 밖에 없다.

하지만 우리는 오름차순으로 스택을 정렬해놨기 때문에, top으로 부터 현재 자기 인덱스까지의 원소 수만큼의 가로 길이를 갖게 된다.▼

 

 

그리고 이 가로길이를 구하는 식이 앞에 적어놨던,

(pop()을 할 때 나온 인덱스에 해당하는 높이 값 * (현재 높이 배열 인덱스 - 스택 top값 - 1))

이 식이다.

그렇게 되면, 각 높이에서 최대 면적이 얼마나 나오는 지를 알 수 있다.

그래서 다시 원래 예제로 돌아오면, 방금 면적은 pop()된 스택 값(인덱스)에 해당하는 높이에서 나올 수 있는 최대값이 되고, 현재 높이 값보다 작은 값들의 인덱스가 전부 pop() 됐다면 이제 현재 높이 값의 인덱스를 넣어준다.▼

 

 

3.이 과정을 높이 배열의 끝에 도달할 때 까지 반복해준다.

1번 과정을 해준다.▼

 

 

작은 값이 나왔으므로 2번 과정을 해준다.▼

 

 

면적 값을 확인했으니, 현재 인덱스를 넣어주고 다시 1번 과정을 반복한다.▼

 

 

마지막 값은 0으로, 다른 값들보다 작을 수 밖에 없으므로 2번 과정을 실행하고, 탐색이 종료된다.▼

 

 

더 큰 값이 없으므로, 최대 면적은 8로 종료된다.

 

 

Swift 코드

---

import Foundation

// 라이노님의 FileIO
final class FileIO {
    private var buffer:[UInt8]
    private var index: Int

    init(fileHandle: FileHandle = FileHandle.standardInput) {
        buffer = Array(fileHandle.readDataToEndOfFile())+[UInt8(0)]
        index = 0
    }

    @inline(__always) private func read() -> UInt8 {
        defer { index += 1 }

        return buffer.withUnsafeBufferPointer { $0[index] }
    }

    @inline(__always) func readInt() -> Int {
        var sum = 0
        var now = read()
        var isPositive = true

        while now == 10
                || now == 32 { now = read() }
        if now == 45{ isPositive.toggle(); now = read() }
        while now >= 48, now <= 57 {
            sum = sum * 10 + Int(now-48)
            now = read()
        }

        return sum * (isPositive ? 1:-1)
    }

    @inline(__always) func readString() -> String {
        var str = ""
        var now = read()

        while now == 10
                || now == 32 { now = read() }

        while now != 10
                && now != 32 && now != 0 {
            str += String(bytes: [now], encoding: .ascii)!
            now = read()
        }

        return str
    }
}

var file = FileIO()
let n = file.readInt()
var height = Array(repeating: 0, count: n + 2)
var stack = [Int]()
var answer = 0

for i in 1...n {
    height[i] = file.readInt()
}

stack.append(0)
for i in 1...n + 1 {
    while (!stack.isEmpty && height[stack.last!] > height[i]) {
        answer = max(answer, height[stack.removeLast()] * (i - stack.last! - 1))
    }
    stack.append(i)
}
print(answer)