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

문제) https://programmers.co.kr/learn/courses/30/lessons/12984

풀이)

이분 탐색을 활용해서 푼 문제이다.

land 중 가장 적은 높이를 start, 가장 큰 높이를 end라고 할 때

비용을 계산해 볼 기준 높이 mid는 mid = (start + end) /2이다.

그리고 기준 높이 mid, 기준 높이 mid + 1의 높이 각자의 비용을 구한 뒤 mid +1 높이의 비용이 더 크다면 mid와 같거나 큰 높이는 더이상 고려하지 않는다고 생각해서 푼다.

코드)

#include<vector>
#include<climits>
using namespace std;

long long cal(long long h,vector<vector<int> > &land, int P, int Q){
    long long val =0;
     for(int i=0;i<land.size();i++){
        for(int j=0;j<land[i].size();j++){
            if(land[i][j] < h){ // 블록 추가해야함 -> P비용사용
                val += (h - land[i][j]) * P;
            }
            else if(land[i][j] > h){// 블록 제거해야함 -> Q비용사용
                val += (land[i][j] - h) * Q;
            }
        }
     }
    return val;
}

long long solution(vector<vector<int> > land, int P, int Q) {
    long long answer = LLONG_MAX;
   //이분탐색
    long long start = LLONG_MAX;
    long long end = 1 , mid = 1;
   for(int i=0;i<land.size();i++){
        for(int j=0;j<land[i].size();j++){
            if(start > land[i][j]) start = land[i][j];
            if(end < land[i][j]) end = land[i][j];
        }
   }

    while(start <= end){
        mid = (start + end)/2; // 블록높이

        long long left = cal(mid, land, P, Q);
        long long right = cal(mid+1, land, P, Q);

        if(left < right){
            answer = left;
            end = mid -1;
        }
        else{
            answer = right;
            if(left == right) break;
            start = mid+1;
        }
    }

    return answer;
}

+ 풀이의 문제점 : 시간 기준을 아슬아슬하게 통과한다.

 처음에 효율성 검사를 통과 못하길래, 비용을 계산하는 cal()함수에 전달되는 land 배열을 & 참조로 넘겨줘서 통과시켰다. 

+ 다른 풀이 : 다른 분의 해설을 통해 시간을 줄일 수 있는 다른 방법을 알아보았다.

                  land를 1차원으로 바꾼 뒤, 각 층수별로 비용계산하는 방법이다. 

 층수를 오름차순으로 정렬 후, 현재 층수에서 이전 층수들은 높이를 높여야할 층수로 보고, 현재 층수에서 이후 층수들을 높이를 낮춰야할 층수로 생각해서 비용을 구하는 방법이었다.

 참고 주소 (https://ydeer.tistory.com/78)

다른 풀이의 코드)

#include<vector>
#include<climits>
#include <algorithm>
using namespace std;
 
long long solution(vector<vector<int> > land, int P, int Q) {
    long long answer = LLONG_MAX;
    //모든 층수를 확인
    vector <long long> height;
    long long total = 0; // 총 블럭 수
    for(int i=0;i<land.size();i++){
        for(int j=0;j<land[i].size();j++){
            height.push_back(land[i][j]);
            total += land[i][j];
        }
    }
    sort(height.begin(),height.end());//오름차순 정렬
    
    long long last = -1;//이전에 계산한 층수 값
    long long block = 0;//이전 층수들의 높이 합
    for(int i=0;i<height.size();i++){
        if(last != height[i]){
            //높여야할 층수 
            long long up = height[i] * i - block; //i인덱스 전까지 있어야할 높이 합 - i인덱스 이전까지 높이 합
            //낮춰야할 층수 
            long long down = total - block - height[i] * (height.size() - i); //i인덱스부터 그 이후로 낮춰야할 높이 합
            long long val = up*P + down*Q;
            if(answer > val) answer = val;
 
            last = height[i];
        }
        block += height[i];
    }
    return answer;
}