2304번 창고 다각형
https://www.acmicpc.net/problem/2304
문제
N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.
- 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
- 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
- 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
- 지붕의 가장자리는 땅에 닿아야 한다.
- 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.
그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.
창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.
기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.
입력
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.
출력
첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.
알고리즘
1. L의 시작점과 끝나는 점을 찾아준다.
2. 배열을 생성해서 L위치에 높이 값을 넣어준다.
3. 스택으로 방향을 왼쪽, 오른쪽으로 나누어서 지붕을 메꿔준다.
왼쪽 : 현재 높이가 이전의 높이보다 작으면, 스택에 넣어주고 아닌경우, 스택에서 pop을 한 뒤, 전 배열값에 현재값을 넣어준다.
오른쪽 : 왼쪽과 동일
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] arr = new int[1001];
int start = Integer.MAX_VALUE;
int end = 0;
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int L = Integer.parseInt(st.nextToken());
int H = Integer.parseInt(st.nextToken());
arr[L] = H;
start = Math.min(L, start);
end = Math.max(L, end);
}
Stack<Integer> height = new Stack<>();
//왼쪽 비교
int temp = arr[start];
for (int i = start + 1; i <= end; i++) {
if(arr[i] < temp) {
height.push(i);
}
else {
while (!height.isEmpty()) {
int x = height.pop();
arr[x] = temp;
}
temp = arr[i];
}
}
height.clear();
//오른쪽 비교
temp=arr[end];
for(int i = end - 1; i >= start; i--){
if(arr[i] < temp) height.push(i);
else {
while (!height.isEmpty()) {
int x = height.pop();
arr[x]=temp;
}
temp=arr[i];
}
}
int result = 0;
for (int i = start; i <= end; i++) {
result += arr[i];
}
sb.append(result).append("\n");
System.out.print(sb);
}
}