창고 다각형 (Java)

www.acmicpc.net/problem/2304

2304번: 창고 다각형

문제 조건을 읽어보면 '지붕의 어느 부분도 오목하게 들어간 부분이 없어야 한다.'라는 조건이 있다. 이 조건은 커졌다 작아졌다 다시 커질 수 없다는 말이고, 그러려면 가장 커지는 최대 지점이 어딘지 알아야 했다.


처음 생각났던 건 왼쪽 → 오른쪽으로 반복을 돌면서 이전보다 큰 값, 또는 작은 값을 분류해서 구분해낼 예정이었으나 가장 커지는 지점이 어딘지 몰라서 구현할 수 없었다.

그래서 생각해낸 방법은 가장 높은 기둥을 기준으로 왼쪽, 오른쪽으로 갈 수록 점점 높이가 작아져야 한다.

예를 들어, 주어진 테스트 케이스에서 가장 높이가 높은 (8, 10)을 가운데에 두고 가장 왼쪽은 (2, 4), 가장 오른쪽은 (15, 8)이다. 왼쪽, 가운데, 오른쪽 약식으로 표현해볼 때 왼쪽과 가운데 사이에는 왼쪽에서 가운데로 갈 수록 점점 커지는 것들만 추려내야 하고 가운데에서 오른쪽으로 갈 수록 점점 작아지는 것들만 추려내야 한다. 또한, 추려낼 때 왼쪽과 오른쪽보다 작은 값은 선택되어서는 안된다.

코드를 짜면서 고려해봐야 할 사항은 아래와 같다.
가장 큰 값이 가운데에 있을지, 왼쪽 또는 오른쪽에 있을지 고려
가장 큰 값이 하나가 아닐 경우 고려
모두 값이 같을 경우 고려


자바로 작성한 코드는 아래와 같다.

package codingTest;

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

public class Beakjoon2304 {
	
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static List<LH> columnList = new ArrayList<>();
	static String sample =
			"7\r\n" + 
			"2 4\r\n" + 
			"11 4\r\n" + 
			"15 8\r\n" + 
			"4 6\r\n" + 
			"5 3\r\n" + 
			"8 10\r\n" + 
			"13 6";
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		// 입력 데이터 세팅
		BufferedReader input = new BufferedReader(new StringReader(sample));	// 샘플 데이터 읽기
		int numberOfColumn = Integer.parseInt(input.readLine());				// 기둥의 개수(N) 읽기
		for (int i = 0; i < numberOfColumn; i++) {								// 위치(L), 높이(H) 목록 읽기
			columnList.add(new LH(input.readLine()));
		}
		
		// 위치(L) 기준 정렬
		Collections.sort(columnList, new Comparator<LH>() {
			@Override
			public int compare(LH o1, LH o2) {
				// TODO Auto-generated method stub
				Integer L1 = (Integer) o1.getL();
				Integer L2 = (Integer) o2.getL();
				return L1.compareTo(L2);
			}
		});
		
		// 다각형 면적 출력
		System.out.println(calcPolygon(numberOfColumn, columnList));
		
	}
	
	static int calcPolygon(int numberOfColumn, List<LH> columnList) {
		// 변수 세팅
		int startH = columnList.get(0).getH();					// 시작 높이
		int endH = columnList.get(numberOfColumn - 1).getH();	// 끝 높이
		int area = 0;											// 다각형 넓이
		
		// 높이 최댓값을 기준으로 왼쪽, 오른쪽을 나눌 것
		List<Integer> Hlist = new ArrayList<>();
		int maxH = 0;
		for (int i = 0; i < numberOfColumn; i++) {
			Hlist.add(columnList.get(i).getH());
			if (maxH < columnList.get(i).getH()) {
				maxH = columnList.get(i).getH();
			}
		}
		// 높이 최댓값 인덱스 (여러 개일 수도 있으니 최소, 최대)
		int index = Hlist.indexOf(maxH);
		int lastIndex = Hlist.lastIndexOf(maxH);
		
		// 시작값 - 최댓값 사이에 있는 값 고르기
		// 최댓값으로부터 왼쪽 영역, 커지는 값
		List<LH> leftList = new ArrayList<>();
		int temp = startH;
		for (int i = 0; i < index + 1; i++) {
			LH current = columnList.get(i);
			if (temp < current.getH()) {
				temp = current.getH();
			}

			if ((current.getH() >= startH) && (current.getH() <= maxH)) {
				if (temp <= current.getH()) {
					leftList.add(current);
				}
			}
		}
		// 왼쪽 넓이 구하기
		for (int i = 0; i < leftList.size() - 1; i++) {
			area += ((leftList.get(i + 1).getL() - leftList.get(i).getL()) * leftList.get(i).getH());
		}
		
		// 최댓값 고르기
		List<LH> maxList = new ArrayList<>();
		for (int i = index; i < lastIndex + 1; i++) {
			LH current = columnList.get(i);
			if (current.getH() == maxH) {
				maxList.add(current);
			}
		}
		// 최댓값 넓이 구하기 (하나일 경우 *1, 여러 개일 경우 그 넓이만큼)
		if (maxList.size() == 1) {
			area += (1 * maxList.get(0).getH());
		} else {
			area += (((maxList.get(maxList.size() - 1).getL() + 1) - maxList.get(0).getL()) * maxList.get(0).getH());
		}
		
		// 최댓값 - 끝값 사이에 있는 값 고르기
		List<LH> rightList = new ArrayList<>();
		temp = endH;
		for (int i = lastIndex; i < numberOfColumn; i++) {
			LH current = columnList.get(i);
			if (temp > current.getH()) {
				temp = current.getH();
			}
			
			if ((current.getH() >= endH) && (current.getH() <= maxH)) {
				if (temp <= current.getH()) {
					rightList.add(current);
				}
			}
		}
		// 오른쪽 넓이 구하기
		for (int i = 0; i < rightList.size() - 1; i++) {
			area += (((rightList.get(i + 1).getL() + 1) - (rightList.get(i).getL() + 1)) * rightList.get(i + 1).getH());
		}
		
		return area;
	}

}

class LH {
	private int L;
	private int H;
	
	public LH(String text) {
		super();
		String[] temp = text.split(" ");
		L = Integer.parseInt(temp[0]);
		H = Integer.parseInt(temp[1]);
	}
	
	public int getL() {
		// TODO Auto-generated method stub
		return L;
	}
	
	public int getH() {
		// TODO Auto-generated method stub
		return H;
	}

	@Override
	public String toString() {
		// TODO Auto-generated method stub
		return "LH [L=" + L + ", H=" + H + "]\n";
	}
}

코드를 짜다보니 생각한대로 하기에는 약간 무리가 있는 것 같이 느껴졌다.
훨씬 간단한 코드가 많기도 해서 찾아서 읽어봤는데 접근법은 비슷했다.

왼쪽, 가운데, 오른쪽을 따로 나눠서 계산하는 것보다는 왼쪽에서 오른쪽으로 가다가 최댓값에서 중단, 그리고 반대로 오른쪽에서 왼쪽으로 가다가 최댓값에서 중단하는 방식으로 코드를 수정해봐도 좋을 것 같다.