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

문제

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

2304번: 창고 다각형

 

풀이

2차원 배열에 넣어서 정렬을 하려고 했지만 2차원 배열 정렬 방법을 잘 몰라서 gidoong이라는 클래스를 만들고 Comparable 인터페이스를 이용해서 정렬했음

 

1. gidoongs[] 에 gidoong 클래스를 차례대로 넣는다.

2. Comparable 인터페이스를 활용하여 compareTo() 메서드를 재정의하여 gidoongs의 x를 기준 오름차순으로 정렬한다.

3. 앞에서부터 넓이를 계산하여 가장 큰 기둥 전까지 sum에 더해준다.

4. 가장 큰 기둥의 인덱스를 저장한다.

5. 뒤에서부터 4에서 저장했던 인덱스까지 넓이를 sum에 더해준다.

6. 가장 큰 기둥의 넓이를 sum에 더해준다.

 

근데 가운데에 가장 큰 기둥이 있으면 틀리는 코드같은데 통과는 된다.

틀리면 가장 큰 기둥의 높이를 따로 저장했다가 그 높이의 기둥의 개수가 여러개면 그 기둥들(왼쪽 끝부터 오른쪽 끝까지)의 범위의 넓이를 6대신 더해주면 되지 않을까 싶다.

 

코드

// 2304번 창고 다각형
// https://www.acmicpc.net/problem/2304

package BAEKJOON;

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

public class Num2304_창고다각형 {
    static class gidoong implements Comparable<gidoong> {
        int x;
        int h;

        public gidoong(int x, int h) {
            this.x = x;
            this.h = h;
        }

        @Override
        public int compareTo(gidoong o) {
            return this.x - o.x;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());

        gidoong[] gidoongs = new gidoong[N];

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

        Arrays.sort(gidoongs);

        // 테스트
//        for (int i = 0; i < gidoongs.length; i++) {
//            System.out.println(gidoongs[i].x + " " + gidoongs[i].h);
//        }

        int sum = 0; // 넓이
        int max = 0;

        // 왼쪽부터 가장 큰 기둥 전까지의 넓이
        int tempX = gidoongs[0].x;
        int tempH = gidoongs[0].h;
        for (int i = 1; i < gidoongs.length; i++) {
            if (tempH - gidoongs[i].h < 0) {
                sum += tempH * (gidoongs[i].x - tempX);
                tempX = gidoongs[i].x;
                tempH = gidoongs[i].h;
                max = i;
            }
        }

        // 오른쪽부터 가장 큰 기둥 전까지의 넓이
        tempX = gidoongs[gidoongs.length - 1].x;
        tempH = gidoongs[gidoongs.length - 1].h;
        for (int i = 0; i < gidoongs.length - max; i++) {
            if (tempH <= gidoongs[gidoongs.length - 1 - i].h ) {
                sum += (tempX - gidoongs[gidoongs.length - i - 1].x) * tempH;
                tempX = gidoongs[gidoongs.length - 1 - i].x;
                tempH = gidoongs[gidoongs.length - 1 - i].h;
            }
        }
        sum += tempH;

        System.out.println(sum);
    }
}