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

2025. 1. 6. 15:38·Algorithm & Data Structures/BOJ

 

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

 

 

 

히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제다. 스택을 써서 아주 풀었다.
히스토그램은 막대들로 이루어진 그래프 같은 건데,
이 막대들을 조합해서 최대한 큰 직사각형을 만들고 그 넓이를 구하는 게 목표다.

먼저 입력으로 막대 개수와 각 막대의 높이를 받아오는데, 
입력이 0이면 종료한다. 
그렇지 않으면 각 히스토그램에 대해 최대 직사각형의 넓이를 계산한다. 
계산의 핵심은 바로 getMaxRectangleArea라는 메서드다.

여기서 스택을 활용해 최대넓이를 갱신한다.

스택에는 막대들의 인덱스를 저장하는데,

현재 막대의 높이가 이전 막대들보다 낮아지면 

스택에서 하나씩 꺼내며 직사각형의 넓이를 계산한다.

꺼낸 막대의 높이를 기준으로 넓이를 구하고,

이걸 최대 넓이와 비교해 갱신한다.

스택이 비어 있으면 막대 하나로 구성된 넓이가 되고,

스택에 값이 남아 있으면 이전 막대들과의 거리를 이용해 너비를 계산한다.

탐색이 끝난 뒤에도 스택에 남아 있는 값들을 처리해 준다.

이렇게 함으로써 히스토그램의 모든 막대를 기준으로

가능한 최대 직사각형을 놓치지 않고 찾아낼 수 있었다.

그리고 이 과정은 높이를 한 번씩만 확인하기 때문에 매우 빠르다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class b6549 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            if (n == 0) break;
            int[] heights = new int[n];
            for (int i = 0; i < n; i++) {
                heights[i] = Integer.parseInt(st.nextToken());
            }
            System.out.println(getMaxRectangleArea(heights));
        }
    }

    private static long getMaxRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        long maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : (i - stack.peek() - 1);
                maxArea = Math.max(maxArea, (long) height * width);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? heights.length : (heights.length - stack.peek() - 1);
            maxArea = Math.max(maxArea, (long) height * width);
        }
        return maxArea;
    }
}

 

'Algorithm & Data Structures > BOJ' 카테고리의 다른 글

b11066. 파일 합치기  (0) 2025.01.10
b1300. K번째 수  (0) 2025.01.08
b12100. 2048(Easy)  (0) 2025.01.03
Lv 2. 이모티콘 할인행사  (0) 2025.01.01
b9466. 텀 프로젝트  (0) 2024.12.31
'Algorithm & Data Structures/BOJ' 카테고리의 다른 글
  • b11066. 파일 합치기
  • b1300. K번째 수
  • b12100. 2048(Easy)
  • Lv 2. 이모티콘 할인행사
Geisha
Geisha
개발 일기
  • Geisha
    Geisha
    Geisha
  • 전체
    오늘
    어제
    • 분류 전체보기 (320) N
      • Algorithm & Data Structures (242) N
        • BOJ (100) N
        • SWEA (1)
        • Programers (137)
        • Data Structures (3)
      • DB (25)
        • SQL (19)
        • RDBMS (2)
      • Java (1)
        • Class (1)
      • Spring (5)
        • Spring MVC (1)
        • Annotations (1)
      • CS (36)
        • 운영체제 (13)
        • 네트워크 (5)
      • Tool (6)
        • Git (5)
        • AWS (1)
      • Project (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    스택
    백트래킹
    구현
    후위순회
    SQL
    투포인터
    알고리즘
    유니온파인드
    algorithm
    baekjoon
    동적계획법
    programmers
    PriorityQueue
    unionfind
    Stack
    이분탐색
    binarySearch
    Union-Find
    BFS
    DynamicProgramming
    dp
    전위순회
    다익스트라
    프로그래머스
    Java
    백준
    경로압축
    dfs
    골드
    Dijkstra
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
Geisha
b6549. 히스토그램에서 가장 큰 직사각형
상단으로

티스토리툴바