[BOJ][2304] 창고 다각형 - JAVA

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

2304번: 창고 다각형

 

- 풀이

 - 구현 문제

 - 위치 순대로 정렬 후 가장 큰 높이를 구하고, 가장 큰 높이의 마지막 index를 구한다. (가장 큰 높이가 여러 개 일 경우 커버)

 - 0 ~ 가장 큰 높이의 마지막 index 까지 높아질 때마다 면적을 계산하고

 - n-1 ~ 가장 큰 높이의 마지막 index 까지 높아질 때마다 면적을 계산하면

 - 움푹 패인 곳이 없는 창고를 지을 수 있게 된다.

 

 - 후기 & 피드백

 : 답 아이디어까지는 빨랐으나 실제 코드 구현시간이 조금 늦었다. 

 

import java.util.*;
import java.util.stream.Collectors;

public class Main {

    static class Point {
        int L;
        int H;

        public Point(int l, int h) {
            L = l;
            H = h;
        }

        public int getL() {
            return L;
        }
    }

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int answer = 0;
        int maxHeight = 0;
        int n = sc.nextInt();
        List<Point> arr = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int L = sc.nextInt();
            int H = sc.nextInt();
            arr.add(new Point(L, H));
            maxHeight = Math.max(maxHeight, H);
        }

        arr.sort(Comparator.comparingInt(Point::getL));

        int highestIdx = arr.stream().map(e -> e.H).collect(Collectors.toList()).lastIndexOf(maxHeight);

        int lastLocation = 0;
        int idxHeight = 0;
        for (int i = 0; i <= highestIdx; i++) {
            int curLocation = arr.get(i).L;
            int curHeight = arr.get(i).H;
            if (idxHeight < curHeight) {
                int areaVal = idxHeight * (curLocation - lastLocation);
                idxHeight = curHeight;
                lastLocation = curLocation;
                answer += areaVal;
            }

            if (i == highestIdx) {
                int areaVal = idxHeight * (curLocation - lastLocation + 1);
                idxHeight = curHeight;
                lastLocation = curLocation;
                answer += areaVal;
            }
        }

        idxHeight = 0;
        for (int i = n-1; i >= highestIdx; i--) {
            int curLocation = arr.get(i).L;
            int curHeight = arr.get(i).H;
            if (idxHeight < curHeight) {
                int areaVal = idxHeight * (lastLocation - curLocation);
                idxHeight = curHeight;
                lastLocation = curLocation;
                answer += areaVal;
            }
        }

        System.out.println(answer);
    }
}

 

2회차 풀이 (가장 높은 인덱스를 구하는 과정 생략 후 더하는 방법)

import java.util.*;

public class Solution {

    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = Integer.parseInt(sc.nextLine());
        List<Figure> arr = new ArrayList<>();
        for (int i = 0; i < t; i++) {
            String s = sc.nextLine();
            int pos = Integer.parseInt(s.split(" ")[0]);
            int h = Integer.parseInt(s.split(" ")[1]);
            arr.add(new Figure(pos, h));
        }

        arr.sort((a, b) -> a.pos - b.pos);

        int prevIdx = arr.get(0).pos;
        int prevHeight = arr.get(0).h;
        int answer = 0;
        int highestHeight = arr.get(0).h;
        for (int i = 1; i < arr.size(); i++) {
            int currIdx = arr.get(i).pos;
            int currHeight = arr.get(i).h;
            if (prevHeight <= currHeight) {
                answer += (currIdx - prevIdx) * prevHeight;
                prevIdx = currIdx;
                prevHeight = currHeight;
                highestHeight = currHeight;
            }
        }

        if (prevHeight == highestHeight) {
            answer += highestHeight;
        }

        prevIdx = arr.get(arr.size() - 1).pos;
        prevHeight = arr.get(arr.size() - 1).h;
        for (int i = arr.size() - 2; i > 0; i--) {
            int currIdx = arr.get(i).pos;
            int currHeight = arr.get(i).h;
            if (prevHeight < currHeight) {
                answer += (prevIdx - currIdx) * prevHeight;
                prevIdx = currIdx;
                prevHeight = currHeight;
            }
        }

        System.out.println(answer);

    }
}

class Figure {
    int pos;
    int h;

    public Figure(int pos, int h) {
        this.pos = pos;
        this.h = h;
    }
}