[Baekjoon] 2304_창고 다각형

문제(출처: https://www.acmicpc.net/problem/2304)

---

< 창고 다각형 >

 

문제 풀이 

 

가장 높은 막대 기둥을 기준으로 왼쪽과 오른쪽에서 시작하여 기둥의 넓이를 구한다. 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Stack;
import java.util.StringTokenizer;

public class _2304_ { // 창고 다각형

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

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

		ArrayList<int[]> list = new ArrayList<>();
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(bf.readLine());

			int L = Integer.parseInt(st.nextToken());
			int H = Integer.parseInt(st.nextToken());

			list.add(new int[] { L, H });
		}

		Collections.sort(list, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});

		Stack<int[]> stack = new Stack<>();
		stack.add(list.get(0));
		int result = 0;
		for (int i = 1; i < N; i++) {
			if (stack.peek()[1] < list.get(i)[1]) {
				int info[] = stack.pop();
				result += (list.get(i)[0] - info[0]) * info[1];
				stack.add(list.get(i));
			}
		}

		stack.add(list.get(N - 1));
		for (int i = N - 1; i >= 0; i--) {
			if (stack.peek()[1] < list.get(i)[1]) {
				int info[] = stack.pop();
				result += (info[0] - list.get(i)[0] ) * info[1];
				stack.add(list.get(i));
			}
		}

		int info[]=stack.pop();
		if (info[0] == stack.peek()[0]) {
			result += stack.peek()[1];
		} else {
			result += (info[0] + 1 - stack.peek()[0]) * stack.peek()[1];
		}
		System.out.println(result);
	}
}

변수)
N : 기둥의 개수
L, H : 기둥 왼쪽면의 위치, 높이 
stack : Stack <int []>
result : 창고 다각형의 면적

 

기둥의 개수 N을 입력받는다. 기둥의 개수만큼 기둥을 입력받아 ArrayList에 저장한다. ArrayList를 기둥의 왼쪽 면의 위치를 기준으로 오름차순 정렬한다. 

 

Stack에 ArrayList 왼쪽부터 넣으면서 stack의 peek 값보다 클 때 stack에서 값을 뽑아 면적을 구해 더한다. 오른쪽에서부터 넣으면서 stack의 peek 값보다 클 때 stack에서 값을 뽑아 면적을 구해 더한다.

 

stack에서 값을 뽑아 최댓값의 위치를 구해 면적을 더한다. 최종 result를 출력한다. 

---

---