[백준] JAVA - 2304.창고 다각형

생각

주어진 기둥에서 가장 큰 높이가 천막을 치는것을 결정하므로 왼쪽부터 시작하는 포인터와 오른쪽부터 시작하는 포인터를 잡아서 서로 좁혀지는 모양으로 영역을 구하자고 생각했습니다.

 

영역을 구하기 쉽게 정수 x 좌표를 담고 있는 배열을 생성하고 주어진 입력값에 해당하는 높이값을 넣어줬습니다. 이렇게 하면 하나의 막대 영역을 차례대로 더해줘서 계산할때 편리합니다. (이전 알고리즘 스터디때 풀었던 백준 14719 빗물도 이런 방법으로 영역을 구하면 쉽게 구할 수 있습니다!!)

 

가장 왼쪽의 x좌표값을 구하기 위해 x좌표의 최소값을 구해줍니다. 동일한 방법으로 가장 오른쪽의 x좌표값은 x좌표의 최대값을 찾아주면 됩니다.

그 다음으로 가장 높은 높이를 가진 x좌표를 구하기 위해서 반복문을 돌면서 h[maxIdx] < h[i] 일때 maxIdx = i 와 같이 갱신하면서 x좌표를 찾아냅니다.

 

영역의 높이를 결정짓는건 현재까지 지나쳐온 높이들 중 가장 큰 높이가 결정합니다. 따라서 각 영역을 구할때는 현재높이보다 큰 높이가 나온다면 높이를 갱신해주고 더해줍니다.

 

 

Java code

package com.java.algorithm;

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

public class Baekjoon_2304_창고다각형 {
	static int N;
	static int[] h;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		h = new int[1001];
		
		int maxIdx = 1;
		int startIdx = Integer.MAX_VALUE;
		int endIdx = Integer.MIN_VALUE;
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			
			startIdx = Math.min(startIdx, x); // 시작 x좌표값
			endIdx = Math.max(endIdx, x);//마지막 x좌표값
			h[x] = y;
			
			if(h[maxIdx] < h[x]) {
				maxIdx = x; //최대높이를 가진 x좌표값
			}
		}
		int left = left(startIdx, maxIdx);
		int middle = h[maxIdx];
		int right = right(endIdx, maxIdx);
		
		System.out.println(left+middle+right);
	}
	
	//오른쪽영역
	private static int right(int start, int mid) {
		int sum = 0;
		int height = 0;
		for (int i = start; i > mid; i--) {
			height = Math.max(height, h[i]);
			sum += height;
		}
		
		return sum;
	}
	//왼쪽영역
	private static int left(int start, int mid) {
		int sum=0;
		int height = 0;
		for (int i = start; i < mid; i++) {
			height = Math.max(height, h[i]);
			sum += height;
		}

		return sum;
	}

}