[백준 / JAVA] 2304번 창고 다각형

문제

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

접근

먼저 기둥 입력이 위치 순으로 이루어지지 않음.
위치, 높이를 입력할 수 있는 기둥 클래스를 만들고 배열로 선언. 값을 입력 받은 후 위치 오름차순으로 정렬.

기둥의 높이가 가장 높은 것을 pivot으로 잡고

1. 왼쪽 끝 기둥을 highIndex로 설정. 0 ~ pivot 까지 돌면서 highIndex보다 높은 기둥을 만나면 highIndex - 해당 기둥까지의 넓이를 더함. highIndex을 해당 기둥의 index로 초기화.
   

2. 오른쪽 끝 기둥을 highIndex로 설정. (n - 1) ~ pivot 까지 돌면서 highIndex보다 높은 기둥을 만나면 highIndex - 해당 기둥까지의 넓이를 더함. highIndex을 해당 기둥의 index로 초기화.
   

3. pivot 기둥의 넓이를 더함.
   

위의 접근으로 코드를 구현하였으나 최초에는 오답 처리됨.

반례를 찾아보니, 가장 높은 기둥이 여러개 있는 경우는 고려하지 못했음.
ex)
4
1 1
2 1
3 1
4 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].high < columns[i].high) pivot = i;
        }

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

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

        // pivot 기둥의 넓이
        area += columns[pivot].high;

        System.out.println(area);
    }

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

        public column(int location, int high) {
            this.location = location;
            this.high = high;
        }

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

정리

생각보다 많은 시간이 걸린 문제. 반례를 질문 게시판에서 찾는 것보다 스스로 생각해볼 필요가 있을 것 같음. 특이 케이스, 경계값 등.

다른 풀이가 있을까 싶어서 찾아보니 스택을 활용하는 풀이도 있음. 하지만 유의미한 차이는 없다고 생각함.