백준 2304번 창고 다각형 (JAVA)

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

2304번: 창고 다각형

 

저는 스택 개념을 이용해 문제를 해결하였습니다.

저는 왼쪽, 오른쪽에서 각각 진행하며, 만약 이전의 높이보다 크다면 결과값에 너비 * 이전 높이를 더해주었습니다.

그렇게 되면 제일 높은 값의 지붕 값은 고려되지 않습니다. 그래서 왼쪽 오른쪽에서 진행하면서 마지막의 인덱스를 저장해 놓고 그 사이 값 * 해당 높이를 결과값에 더해주어 문제를 해결하였습니다.

 

package BOJ.etc;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_2304 {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Function<String,Integer> stoi = Integer::parseInt;
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = stoi.apply(st.nextToken());
        List<int[]> list = new ArrayList<>();
        for(int i = 0 ; i < n ; i++){
            st = new StringTokenizer(br.readLine());
            int a = stoi.apply(st.nextToken());
            int b = stoi.apply(st.nextToken());
            list.add(new int[]{a,b});
        }
        Collections.sort(list,(v1,v2)->{
            return v1[0] - v2[0];
        });
        int prevHeight = 0;
        int prevIndex = 0;
        int result = 0;
        for(int i = 0 ; i < n ; i++){
            if(prevHeight < list.get(i)[1]){
                result += (list.get(i)[0] - prevIndex) * prevHeight;
                prevIndex = list.get(i)[0];
                prevHeight = list.get(i)[1];
            }
        }
        int firstIndex = prevIndex;
        int tempHeight = prevHeight;
        prevHeight = 0;
        prevIndex = 0;
        for(int i = n-1 ; i >= 0 ; i--){
            if(prevHeight < list.get(i)[1]){
                result += (prevIndex - list.get(i)[0]) * prevHeight;
                prevIndex = list.get(i)[0];
                prevHeight = list.get(i)[1];
            }
        }
        int secondIndex = prevIndex;
        result += (secondIndex - firstIndex + 1) * tempHeight;
        System.out.println(result);
    }
}

2304번: 창고 다각형