프로그래머스 - 지형 편집

문제

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

프로그래머스

지형의 블록 높이가 동일하도록 변경하는 cost 값의 최솟값을 구하는 문제였다.

 

문제 풀이

처음에는 각 높이의 count를 map에 저장하고 각각의 높이에 대해서만 계산하도록 했는데, 계산을 할 때 완전 탐색으로 계산해서 최악의 경우 O(n^2)의 시간이 걸려 실패했고 누적합을 이용해 다시 풀었다.

 

이상한 점은 cost를 구하는 반복문 안에

if(l[i] == l[i-1]) continue;

조건을 추가하면 실패한다. 시간을 크게 줄일 수 있는 조건은 아니라서 그냥 뺐는데 이 조건이 있을 때는 왜 실패하는 건지 모르겠다.

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

void printVector(vector<int> v){
    for(int i=0;i<v.size();i++){
        printf("%d ",v[i]);
    }
    printf("\n\n");
}

long long solution(vector<vector<int>> land, int P, int Q) {
    long long answer = -1;
    int n = land.size()*land.size();
    vector<int> l;    
    vector<long long> landSum(n); //누적합
        
    if(n == 1) return 0;
    
    for(int i=0;i<land.size();i++){
        for(int j=0;j<land.size();j++){
            l.push_back(land[i][j]);
        }
    }    
    sort(l.begin(), l.end());
    
    //누적합 계산
    landSum[0] = l[0];
    for(int i=1;i<n;i++){
        landSum[i] = landSum[i-1] + l[i];
    }

    long long plus, minus, cost;
    int height;
    
    //0일 때 구하기
    answer = (landSum[n-1] - (n)*l[0]) * Q; //추가하는 경우 없음
    
    for(int i=1;i<n;i++){         
        height = l[i];
        plus = ((i) * height) - landSum[i-1]; //0~i-1
        minus = (landSum[n-1] - landSum[i]) - ((n-(i+1)) * height); //i+1 ~ n
        cost = plus*P + minus*Q;
        
        if(cost < answer) answer = cost;        
    }
    
    return answer;
}