[알고리즘] 백준2304 창고다각형 - 자바

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

2304번: 창고 다각형

 

 

[풀이 코드]

package day0209;

// 세상에서 제일 어렵게 풀기
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 백준2304_창고 {
	static int[][] array;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int N = Integer.parseInt(br.readLine());
		array = new int[N][2];
		int sum = 0;
		int maxIndex = 0;
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken()); 
			int y = Integer.parseInt(st.nextToken());
			if(sum < y) {
				sum = Math.max(sum, y);
				maxIndex = x;
			}
			array[i][0] = x;
			array[i][1] = y;
		}

		// 이차원 배열 정렬하기
		Arrays.sort(array, new Comparator<int[]>() {
			@Override
			public int compare(int[] arg0, int[] arg1) {
				if(arg0 == arg1) {
					return arg0[1] - arg1[1];
				}else {
					return arg0[0] - arg1[0];
				}
			}
			
		});
		
		//왼쪽부터
		int temp = 0;
		int idx = 0;
		for(int i=0; i<maxIndex; i++) { 
			int xi = array[idx][0];
			if (i != xi) {
				sum += temp;
				continue;
			}
			
			if (array[idx][1] > temp) { //이전 height보다 높다면 temp 변경해주기
				temp = array[idx][1];
				idx++;
				sum += temp;
			}else { // 이전 height인 temp가 높다면 temp유지하기
				idx++;
				sum += temp;
			}
		}
		
		//오른쪽부터
		temp = 0;
		idx = N-1; //15
		for(int i=array[idx][0]; i>maxIndex; i--) {
			int xi = array[idx][0];
			if(i != xi) {
				sum += temp;
				continue;
			}
			
			if(array[idx][1] > temp) {
				temp = array[idx][1];
				idx--;
				sum += temp;
				continue;
			}else {
				idx--;
				sum += temp;
				continue;
			}
			
			
		}
		
		System.out.println(sum);
		
	}

}

• 제일 높은기둥을 찾아서 그 기둥의 index와 height를 2차원 배열에 정렬해주면서 따로 변수에 담았다. maxIndex에 담긴 높은기둥의 인덱스를 기준으로 왼쪽, 오른쪽 방향으로 for문을 돌려주려고 생각했다.
  
  
• 파이썬에서는 이차원배열 정렬을 람다식으로 정말 간단하게 할 수 있어서 당연히 쉽게 될 줄 알았지만.. 자바는 달랐다. comparator를 import 해서 compare메서드를 오버라이딩해줘야 했다.
  
  
• 정렬된 2차원 배열을 돌면서 왼쪽 방향으로 maxIndex까지 0 + 0 + 4 + 4 + 8 + 8 + 8 + 8이 담기도록 했고, 오른쪽 방향으로는 8 + 8 + 8 + 8 + 8 + 8 + 8 이 담기도록 했다. 제일 높은 10은 2차원 배열을 담을 때 미리 더해놨다.