[백준 2304 / Java / 실버2] 창고 다각형

문제

 

처음 문제를 보고,  이분탐색인가? 그리디인가? 어떤 알고리즘이지? 고민했는데,

결국 그냥 구현이었다.

 

import java.io.*;
import java.util.*;

public class 창고_다각형_2304 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		/**
		 * 가장 작은 창고 면적 구하기
		 * 한번 내려가면 다시 올라오면 안된다
		 * 
		 * 올라가기: 기존 높이로 쭉 진행하며, 높은 걸 만날때마다 올라간다
		 * 내려가기: 가장 높은 곳에 도달했다면, 내려갈 준비를 한다
		 *     1. 남은 기둥 중 가장 높은 높이로 내려간 후 해당 기둥까지 진행한다
		 *     2. 남은 기둥이 없다면 종료한다.
		 */
		
		int N = Integer.parseInt(br.readLine());
		
		/** 기둥들 입력받기 */
		int[][] columns = new int[N][2];
		for (int i = 0; i < N; i++) {
			
			st = new StringTokenizer(br.readLine());
			int location;
			int height;
			
			location = Integer.parseInt(st.nextToken());
			height = Integer.parseInt(st.nextToken());
			
			// [위치, 높이, 인덱스]
			columns[i] = new int[] {location, height, i};
		}
		Arrays.sort(columns, (a, b) -> a[0] - b[0]);  // 위치 순서대로 기둥 정렬
		
		/** 기둥이 1개라면 즉시 종료 */
		if (N == 1) {
			System.out.println(columns[0][1]);
		}
		
		/**
		 * 올라갈때: 기둥높이 * 다음기둥까지의 거리 = 면적
		 * 최고점 왔을때: 올라갈때 값에 추가로 현재기둥높이 더한 후, 내려가기 로직으로 전환
		 * 내려갈때: 다음기둥 없으면 그대로 종료, 있으면 다음기둥높이 * 다음기둥까지의 거리
		 */
		else {
			
			int[] highestColumn = findHighestColumn(columns, 0);  // 최고높이 컬럼(전환점)
			int[] prev = columns[0];  // 이전 기둥
			int result = 0;  // 결과 면적
			
			/** 올라갈 때 */
			for (int i = 1; i < N; i++) {
				
				// 최고 높이 기둥 만났을 경우, 면적 더하고 내려가기 로직으로 전환
				if (columns[i][0] == highestColumn[0]) {
					result += prev[1] * (columns[i][0] - prev[0]);
					result += columns[i][1];  // 최고기둥 자체 높이 추가로 더해야 함
					break;
				}
				
				// 높은 기둥 만났을 경우 면적 더하기
				else if (columns[i][1] >= prev[1]) {
					result += prev[1] * (columns[i][0] - prev[0]);
					prev = new int[] {columns[i][0], columns[i][1], i};
				}
			}
			
			/** 내려갈 때 */
			prev = highestColumn;
			int[] nextColumn = findHighestColumn(columns, prev[2] + 1);
			while (nextColumn != null) {
				
				result += nextColumn[1] * (nextColumn[0] - prev[0]);
				prev = nextColumn;
				nextColumn = findHighestColumn(columns, prev[2] + 1);  // 다음 기둥이 존재하면 계속 내려가기
			}
			System.out.println(result);
		}
	}
	
	/** 지정된 인덱스부터 끝까지 탐색하여, 가장 높은 기둥 정보(위치, 높이, 인덱스)를 리턴하는 함수 */
	private static int[] findHighestColumn(int[][] arr, int idx) {
		
		/** 남은 기둥이 없다면 null 리턴 */
		if (idx >= arr.length) {
			return null;
		}
		
		// 위치, 높이, 인덱스
		int highestColumn[] = new int[] {0, 0, 0};
		for (int i = idx; i < arr.length; i++) {
			
			if (arr[i][1] >= highestColumn[1]) {
				highestColumn[0] = arr[i][0];
				highestColumn[1] = arr[i][1];
				highestColumn[2] = i;
			}
		}
		return highestColumn;
	}
}

 

면적을 계산하는 로직을 파악한 후, 그대로 구현했다. 딱히 대단한 알고리즘은 사용하지 않았다.

 

N이 최대 1000이라, N^2 복잡도로 구현한다고 해도 100만번 연산이라 매우 여유롭다. 실제로 내 코드도 O(N^2) 이다. findHighestColumn이 한번 호출 당 N의 복잡도를 갖기 때문이다.

 

우선, 최고점 기둥을 파악해야 한다. 최고점 기둥을 기준으로 적용되는 로직이 바뀐다. 올라가는 로직, 내려가는 로직을 분리해서 처리해야 한다.

 

최고점 기둥을 만날 때 까지, 기둥 순서대로 진행하며 더 높은 기둥을 만나면 해당 높이로 무조건 올라간다.

최고점 기둥을 만나면, 해당 부분까지만 면적을 구해놓은 후 내려가는 로직으로 전환한다.

내려가는 로직에서는, findHighestColumn 함수를 이용해 남은 기둥 중 가장 높은 기둥을 찾고, 해당 기둥까지의 면적을 계산한다.

이때 while문으로 진행하기 때문에 다음 기둥이 없다면 자동으로 루프는 종료되며,

마지막에 계산된 면적을 출력해주면 된다.

 

구현이다 보니까 여러 데이터를 복잡하게 관리해야 하고 실수할 부분이 많아 좀 헤맸다. 코드 작성 후 이게 풀릴까? 싶은 마음으로 제출해 봤는데 한번에 맞았고..(물론 IDE에서 디버깅은 거침) 다른 사람들 코드도 참고해본 결과, 대단한 알고리즘으로 효율적으로 푸는 문제가 아니라 그냥 구현 문제였다. 내 코드가 틀리지 않았다는 것..

 

 

결과

 

N이 최대 1000으로 작다 보니까 딱히 시간이 많이 걸리지도 않았다.

가운데 컴파일 에러는 클래스명 Main으로 안 바꿔서 생긴 오류.