[백준] 2304번: 창고 다각형 - Java

문제

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

여러 개의 기둥이 주어졌을 때, 이 기둥들을 사용해 만든 창고의 지붕 면적을 구하는 문제입니다. 각 기둥은 위치와 높이로 정의되며, 모든 기둥의 폭은 1입니다.

 

접근 방법

• 기둥 배열 정렬: 기둥들을 위치에 따라 오름차순으로 정렬합니다.
• 최고 높이의 기둥을 중심으로 면적 계산:
  • 왼쪽에서 최고 기둥까지: 왼쪽에서 오른쪽으로 진행하면서 높이가 증가할 때마다 면적을 계산합니다.
  • 오른쪽에서 최고 기둥까지: 오른쪽에서 왼쪽으로 진행하면서 높이가 증가할 때마다 면적을 계산합니다.
• 최고 높이의 기둥 면적 추가: 마지막으로 최고 높이의 기둥 면적을 더해줍니다.

 

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        Column[] columns = new Column[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            columns[i] = new Column(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        Arrays.sort(columns); // 기둥 배열을 위치 오름차순으로 정렬

        int area = 0; // 창고 면적을 누적
        int pivot = 0;

        // 가장 높은 기둥을 pivot으로 설정
        for (int i = 0 ; i < n; i++) {
            if (columns[pivot].height < columns[i].height) pivot = i;
        }

        // 가장 왼쪽 기둥부터 pivot까지 면적 계산
        int highestIndex = 0;
        for (int i = 0; i <= pivot; i++) {
            if (columns[highestIndex].height <= columns[i].height) {
                area += (columns[i].location - columns[highestIndex].location) * columns[highestIndex].height;
                highestIndex = i;
            }
        }

        // 가장 오른쪽 기둥부터 pivot까지 면적 계산
        highestIndex = n - 1;
        for (int i = n - 1; i >= pivot; i--) {
            if (columns[highestIndex].height <= columns[i].height) {
                area += (columns[highestIndex].location - columns[i].location) * columns[highestIndex].height;
                highestIndex = i;
            }
        }

        // pivot 기둥의 넓이 추가
        area += columns[pivot].height;

        System.out.println(area);
    }

    // 기둥 클래스, x 좌표와 높이로 구성
    public static class Column implements Comparable<Column> {
        public int location;
        public int height;

        public Column(int location, int height) {
            this.location = location;
            this.height = height;
        }

        // 위치 오름차순을 위해 함수 오버라이딩
        @Override
        public int compareTo(Column c) {
            return this.location - c.location;
        }
    }
}

 

메모리:14484kb 시간:112ms