[알고리즘 문제] programmers - 지형편집

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

코딩테스트 연습 - 지형 편집 | 프로그래머스

문제 자체는 이해하는데 그렇게 어렵지 않습니다.

1x1x1모양의 블럭이 쌓여져 있습니다. 이 블럭을 다음과 같이 높이가 모두 같도록 만들어 주어야 합니다.. 

그렇다면 블럭이 쌓여있는 위치에서 몇개를 빼거나/추가하는 과정을 거쳐야 겠습니다. 

예를 들어서, 각 블럭의 높이가 4,8,2이라고 가정합니다. 높이를 5라고 한다면, 첫번째(4)에서는 1개를 추가, 두번쨰(8)은 3개를 삭제, 세번째(2)는 3개를 추가를 하면 모든 위치에서 블럭의 높이가 5가 됩니다.

 

여기서 하나의 블럭을 추가할 때의 비용, 삭제 할때의 비용이 문제에서 주어집니다. 만약 추가비용이5, 삭제 비용이 3라면 총 추가/삭제 비용은 비용*블럭의 수가 됩됩니다. 위의 예시에서 높이가 4,8,2이고 추가비용이 5, 삭제비용이 3이라고 해봅시다.

그렇다면 총 비용은 (1 x 5) + (3 x 6) + ( 3 x 5 ) -> 38이 됩니다. 근데 높이 5에서의 비용은 38이지만 만약 x높이라면 비용이 얼마가 될까요 ?

 

출력은 높이5에서의 비용은 38이고 높이 7에서의 비용은 24라고 한다면 24를 출력하면 됩니다. 즉 최소비용을 구하는 문제입니다.

 

첫번째로 생각해본 방법은 각 블럭의 최소/최대 높이를 구하고 그 사이 값을 높이로 했을 때의 비용에서 가장 최소비용을 구하는 것입니다.

가장 직관적인 방법인데, 이렇게 하면 시간복잡도가 O(N^3)이 됩니다. 배열의 크기는 그렇게 크지 않지만, 각 블럭의 높이 범위가 0~10억 이기때문에 최악의 경우 n번 반복을 10억번 할 수도 있습니다.

 

두번째 방법은 각 블럭의 높이저장하는 배열을 돌면서 하나씩 비교하는게 아니라, map을 사용해서 h의 높이를 가진 블럭이 몇개있는지를 저장해 놓습니다. 여기서는 map과 list 자료구조를 사용했는데

list는 각각의 높이를 중복되지 않게 저장하고 높이의 최대/최소값과 map의 key값을 저장합니다.

map은 각 높이의 빈도수를 저장합니다. 

예를들어서 4,8,8,4,2높이의 블럭이 있다면 기존에는 4,8,8,4,2,를 모두 검사를 해주어여 했습니다. 하지만 4와8의 경우는 같은 높이인데도 연산을 한번 더 하기 때문에 4:2, 8:2 처럼 각 높이의 빈도수를 저장하면 한번에 연산을 할 수 있습니다.

 

하지만 이렇게 하면,n높이를 가진 k개의 블럭의 비용을 한번에 구할 수 있지만 여기 list를 만드는데 contain()메소드의 시간복잡도가 O(n)이기 때문에 이 경우도 시간을 많이 잡아먹기 때문에 두번째 방법도 그렇게 효율적이진 않습니다.

 

세번째 방법은 parametric search를 사용하는 방법입니다. 이 방법은 다른분의 아이디어를 참고하였습니다. 이 방법은 이분탐색을 사용하는데 updown게임에서 특정숫자를 찾기 위해 1/2씩 줄여나가는 방법과 비슷합니다. 먼저 s(높이의 최소값)와 e(높이의 최대값)의 가운데 값 mid와 mid+1에서의 비용을 구합니다.

먼저 mid+1의 비용이 mid1의 비용보다 더 크다고 가정해 봅시다. 우리는 가장 작은 비용을 찾고있기 떄문에 더 큰값은 필요하지 않습니다. 그 말은 mid+1보다 같거나 큰 높이에서는 고려할 필요가 없다는 것이겠죠. 같은 얘기로, updown게임에서 우리가 찾는 숫자가 14이고 그 값이 15보다 큰지 물었는데 크다고 한다면 더이상 15이상의 숫자를 물어보지 않겠죠. 같은 맥락입니다. 

이런 과정을 반복하면서 비용이 가장 낮은 높이를 구할 수 있습니다.

 

두번쨰 과정에서는 getCost()함수의 시간복잡도를 O(n)으로 만들었었는데, 배열의 크기가 생각보다 크지 않아서 O(n^2)으로 해도 전체 연산속도에 영향을 크게 주지 않네요. 대신 두번째 과정에서는 main함수의 for문을 높이최소~최대 값만큼 반복했고, 지금의 경우는O(logN)만큼 반복했는데, 결과적으로는  parametric search을 사용한 방법이 더 나아 보이네요.

 

정답중에 다양한 방법들이 있었는데, 저는 paramteric search방법이 가장 직관적여 보여서 사용하였습니다.

// https://programmers.co.kr/learn/courses/30/lessons/49993
// 지형편집

public class Solution {
    public long solution(int[][] land, int P, int Q) {

        int y, x, heigth;
        int height = land.length;
        int width = land[0].length;

        long s = 1000000000;
        long e = 0;
        for (y = 0; y < height; y++) {
            for (x = 0; x < width; x++) {
                e = Math.max(e, land[y][x]);
                s = Math.min(s, land[y][x]);
            }
        }

        long mid = 0;

        while (s <= e) {
            mid = (s + e) / 2;
            if (s == e) {
                break;
            }

            long r1 = getCost(mid, land, P, Q);
            long r2 = getCost(mid + 1, land, P, Q);
            if (r1 == r2) {
                break;
            }
            if (r1 < r2) {
                e = mid;
            } else {
                s = mid + 1;
            }
        }
        return getCost(mid, land, P, Q);
    }

    long getCost(long mid, int[][] land, int P, int Q) {
        long result = 0;
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[0].length; j++) {
                if (land[i][j] > mid) {
                    result = result + (land[i][j] - mid) * Q;
                } else if (land[i][j] < mid) {
                    result = result + (mid - land[i][j]) * P;
                }
            }
        }
        return result;
    }
}