2304번 - 창고 다각형

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

2304번: 창고 다각형

 

 

 

 

 

최고점을 기준으로 왼쪽 영역과 오른쪽 영역으로 나눠서 접근해서 풀어야 한다. 처음에 이 풀이법이 생각이 안났다. 다른 사람들의 접근법 이야기를 듣고 알게 되었다!

 

자료구조는 처음에는 기둥 class를 만들어서 L과 H를 넣은 객체를 생성해 ArrayList에 저장하고, Comparator를 오버로딩해서 정렬도 하려고 했었다. 하지만 어느 H값을 가지고 list의 인덱스를 알아내는 것이 안되었다. 그래서 2차원 배열로 바꿔서 인덱스와 L과 H를 저장하도록 했다. 그리고 L값을 기준으로 오름차순 정렬하도록 했다.

 

int[][] arr = new int[N][2];

 

근데 넓이를 구하는 과정이 복잡했다..!

- 

- 

- 

 

 

 

 

 

 

하지만 틀리길 여러 번 끝에 겨우 풀었다. 질문 게시판의 테스트케이스 적용해보며 조금씩 고쳤다.

거의 3시간 동안 열심히 삽질했다ㅎㅎ

 

 

 

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		
		int[][] arr = new int[N][2];
		
		int max = 0;
		int idx = 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[i][0] = L;
			arr[i][1] = H;
		}
		
		//구현
		Arrays.sort(arr, new Comparator<int[]>() { //l 기준 오름차순 정렬
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});
		
		//최고점 구하기
		for(int i = 0; i < N; i++) {
			if(arr[i][1] > max) {
				max = arr[i][1];
				idx = i;
			}
		}
		
		int area = max; //가운데 면적
		
		//왼쪽 면적
		int left_max = 0;
		int left_idx = 0;
		for(int i = 0; i <= idx; i++) {
			if(arr[i][1] >= left_max) {
				area += left_max * (arr[i][0] - arr[left_idx][0]); //이전 최고 높이*이전 좌표
				//갱신
				left_max = arr[i][1];
				left_idx = i;
			}
		}
		
		//오른쪽 면적
		int right_max = 0;
		int right_idx = N - 1;
		for(int i = N - 1; i >= idx; i--) {
			if(arr[i][1] >= right_max) {
				area += right_max * (arr[right_idx][0] - arr[i][0]); //이전 최고 높이*이전 좌표
				//갱신
				right_max = arr[i][1];
				right_idx = i;
			}
		}
		
		//출력
		System.out.println(area);
	}

}

 

 

 

 

 

결과