[BOJ] 2304 창고 다각형 - JAVA

1. 문제

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

2304번: 창고 다각형

창고의 지붕을 다음과 같이 만든다.

1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
4. 지붕의 가장자리는 땅에 닿아야 한다.
5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

---

2. 풀이

1. 먼저 x축을 기준으로 정렬한다.
2. 현재 기둥을 기준으로 그 오른쪽에 현재 기둥보다 큰 기둥이 있다면 그 값, 없다면 옆에 있는 기둥 중 가장 큰 값을 고른다.
3. 위의 결과로 넓이를 구한다. 맨 끝을 prev에 넣은 뒤 그 다음 기둥부터 비교한다. 
   • 만약 이전 기둥이 나보다 크다면 이전 기둥의 높이만 넓이에 더해준다. 그 뒤, prev에 new int[]{이전 기둥의 x좌표-1값, 나의 기둥높이} 새 객체를 넣는다.
   • 이 경우가 아니라면 (이전기둥의 x-나의 x)*이전 기둥 높이를 넓이에 더한다.
   • prev를 현재 기둥으로 교체한다.
4. 항상 마지막 기둥(가장 왼쪽)만큼의 넓이가 빠지므로 더해준다.

import java.io.*;
import java.util.*;

public class BOJ_2304_창고다각형 {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(in.readLine());

        StringTokenizer st;

        int[][] input = new int[N][2];

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(in.readLine());
            input[i][0] = Integer.parseInt(st.nextToken());  //가로
            input[i][1] = Integer.parseInt(st.nextToken());  //높이
        }

        Arrays.sort(input, (o1, o2) -> o1[0] - o2[0]);

        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            //현재 번호에 맞는 기둥을 list에 추가
            list.add(input[i]);

            //현재 번호 기둥의 높이
            int num = input[i][1];

            //나 다음 기둥의 최대값
            int max = Integer.MIN_VALUE;
            for(int j=i+1;j<N;j++){
                //현재 기둥보다 큰 게 있다면 i에 j값을 넣고(for문이라 -1해줌)
                if(num<input[j][1]) {
                    i = j-1;
                    break;
                }
                //없으면 나보단 작지만 그 다음으로 큰 기둥을 저장함
                if(max<input[j][1]) {
                    max = input[j][1];
                    i = j-1;
                }
            }

        }

        int area = 0;
        //맨 끝 기둥
        int[] prev = list.get(list.size()-1);
        for(int i= list.size()-2;i>=0;i--){
            //현재 기둥
            int[] cur = list.get(i);
            //만약 이전 기둥이 나보다 크다면 기둥높이만 더해줌.
            //이전 기둥은 새로 객체 넣어줌 이전기둥 가로-1, 현재기둥 높이
            if(prev[1]>cur[1]) {
                area+=prev[1];
                prev = new int[]{prev[0]-1,cur[1]};
                ++i;
                continue;
            }
            //위의 경우가 아니라면 이전-지금 넓이 더해줌
            area += Math.abs(prev[0]-cur[0])*prev[1];
            //이전꺼 바꿔줌
            prev = cur;
        }

        //맨 끝은 항상 기둥넓이가 안들어가니까 더해줌
        area += prev[1];

        System.out.println(area);
    }
}

---

3. 결과

더 깔끔하게 풀고 싶다.

다시풀었다! --> 2022.03.21 - [코딩테스트/BOJ] - [BOJ] 2304 창고다각형 - JAVA