[자바/Java] 분할선으로 영역을 잘라서 가장 넓은 영역의 넓이 구하기

문제) 첫 줄에는 가로와 세로가 주어지고, 둘째줄에는 분할선의 개수가 주어진다. 가로 분할선일 경우 0과 해당 번호가 주어지고, 세로 분할선일 경우 1과 해당 번호가 주어진다.  분할선으로 분할된 영역 중에서 가장 넓은 영역의 넓이를 출력한다.

 

package practice;

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int w = sc.nextInt(); //가로
		int h = sc.nextInt(); //세로
		int[] wArr = new int[w];
		int[] hArr = new int[h];
		wArr[wArr.length-1] = w;
		hArr[hArr.length-1] = h;
		
		int n = sc.nextInt(); //횟수
		for(int i=0; i<n; i++) {
			int wh = sc.nextInt(); //가로인지 세로인지
			int line = sc.nextInt(); //줄 번호
			
			if(wh==0) {//가로구분선이라면(직사각형 세로에 영향)
				hArr[line] = line;
			}
			if(wh==1) {//세로구분선이라면(직사각형 가로에 영향)
				wArr[line] = line;
			}
		}
		
		//가로, 세로 저장한 값들 순서대로 정렬
		Arrays.sort(wArr);
		Arrays.sort(hArr);
		
		int maxW = 1; //가로 최댓값
		int maxH = 1; //세로 최댓값
		for(int i=w-1; i>0; i--) {
			if(maxW < wArr[i]-wArr[i-1]) {
				maxW = wArr[i]-wArr[i-1];
			}
		}
		for(int i=h-1; i>0; i--) {
			if(maxH < hArr[i]-hArr[i-1]) {
				maxH = hArr[i]-hArr[i-1];
			}
		}
		
		System.out.println(maxW * maxH);
	}
}