프로그래머스 - 지형 편집

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 지형 편집

https://programmers.co.kr/learn/courses/30/lessons/12984?language=java

풀이 : 이분탐색 알고리즘을 사용하되 이차 그래프의 최저점을 알기 위해 mid+1을 통해 기울기 여부를 판단하여 탐색한다.

public class Solution {
    public long solution(int[][] land, int P, int Q) {
       long min = Long.MAX_VALUE;
       long l = Long.MAX_VALUE, r = 0;
       for (int i = 0; i < land.length; i++) {
		for (int j = 0; j < land[0].length; j++) {
			r = Math.max(land[i][j], r);
			l = Math.min(land[i][j], l);
		}
	}
	while(l <= r) {
		long mid = (l + r) / 2;
		long a = getCost(land, mid, P, Q);
		long b = getCost(land, mid+1, P, Q);
		if(a <= b) {
			min = Math.min(min, a);
			r = --mid;
		}else {
			min = Math.min(min, b);
			l = ++mid;
		}
	}
       return min;
    }
    private static long getCost(int[][] land, long mid, int p, int q) {
	long cost = 0;
	for (int i = 0; i < land.length; i++) {
		for (int j = 0; j < land[0].length; j++) {
			int n = land[i][j];
			if(n < mid) cost += (mid - n) * p;
			else cost += (n - mid) * q;
		}
	}
     return cost;
    }
}