[프로그래머스] 지형 편집

문제 설명

https://school.programmers.co.kr/learn/courses/30/lessons/12984

문제 풀이

• 두가지 풀이가 존재한다. 1)이분 탐색 2)쉬운 아이디어
• 우선 문제에서 존재하는 블록의 높이의 범위를 min ~ max라고하고 블록을 n개로 맞추었을 때 결과값을 result라고하면 n을 x축으로 하고 min에서 max로 증가함에 따라 result의 값을 y축으로 했을 때 V자 형태(변곡점 존재)의 결과가 나오게 된다.
• 이를 활용하여 아래 2가지 풀이가 나올 수 있다.

1. 이분 탐색 (내가 풀이한 코드)
   - 높이를 대상으로 이분탐색을 진행한다.
   - 특정 mid에서 코스트가 mid-1의 코스트와 mid+1의 코스트보다 작으면 이분탐색을 종료한다. (변곡점)
   - 시간 복잡도 : O(NxNxlog(H)) (H: 블록의 높이값, 10억)
   - 최악의 경우 시간 초과가 발생할 듯 했으나 운이 좋은듯..
2. 쉬운 아이디어 (다른 사람 풀이 참조)
   - 전체 블록들을 1차원 배열에 놓고 정렬한다.
   - 이때 0번 블록부터 차례로 증가시켜가며 해당 블록의 높이로 모두 맞춰 코스트 계산한다. (O(1))
   - 이 때 특정 인덱스의 코스트가 그 다음 인덱스의 코스트보다 작다면 멈춰준다. (변곡점)
   - 시간 복잡도 : O(NxN)

소스 코드 (JAVA, 이분탐색)

public class Solution {
    public long solution(int[][] land, int P, int Q) {
        int N = land.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                min = Math.min(min, land[i][j]);
                max = Math.max(max, land[i][j]);
            }
        }

        int lo = min;
        int hi = max + 1;
        while(lo + 1 < hi) {
            int mid = (lo + hi) / 2;

            //결과 계산
            long left = 0;
            long cur = 0;
            long right = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (mid - 1 >= 0) {
                        left += (land[i][j] > mid - 1) ? (long)(land[i][j] - mid + 1) * Q : (long)(mid - 1 - land[i][j]) * P;
                    }
                    if (mid + 1 <= max) {
                        right += (land[i][j] > mid + 1) ? (long)(land[i][j] - mid - 1) * Q : (long)(mid + 1 - land[i][j]) * P;
                    }
                    cur += (land[i][j] > mid) ? (long)(land[i][j] - mid) * Q : (long)(mid - land[i][j]) * P;
                }
            }

            if (mid - 1 < min) {
                if (cur < right) hi = mid;
                else lo = mid;
            } else if (mid + 1 > max) {
                if (cur > left) hi = mid;
                else lo = mid;
            } else {
                if (cur <= left && cur <= right) {
                    lo = mid;
                    break;
                } else if (cur > left) {
                    hi = mid;
                } else
                    lo = mid;
            }
        }

        long result = 0;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                result += (land[i][j] > lo) ? (long)(land[i][j] - lo) * Q : (long)(lo - land[i][j]) * P;
            }
        }
        return result;
    }
}