문제 개요
가격 배열 P = [p₁, p₂, ..., pₙ]와 목표 값(target)이 주어졌을 때, 각 가격 Pᵢ를 Roundᵢ(Pᵢ)로 반올림하여 반올림된 배열 [Round₁(P₁), Round₂(P₂), ..., Roundₙ(Pₙ)]의 총합이 목표 값과 정확히 일치하도록 만들어야 합니다. 여기서 각 반올림 연산 Roundᵢ(pᵢ)는 내림(Floor) 또는 올림(Ceil) 중 하나만 사용할 수 있습니다.
반올림된 배열의 합을 목표 값으로 맞추는 것이 불가능한 경우에는 문자열 "-1"을 반환합니다. 가능하다면 아래 수식으로 정의되는 최소 반올림 오류를 계산하여, 소수점 세 자리까지 포함하는 문자열 형태로 반환해야 합니다.
∑ (i = 1 ~ n) |Roundᵢ(Pᵢ) − Pᵢ|
예를 들어 입력이 ["0.700", "2.800", "4.900"]이고 목표 값이 8이라면, 내림과 올림을 적절히 조합하여 (0.7 − 0) + (3 − 2.8) + (5 − 4.9) = 0.7 + 0.2 + 0.1 = 1.000이라는 결과를 얻을 수 있습니다.
알고리즘 접근 방법
이 문제는 그리디(Greedy) 기법과 우선순위 큐(priority queue)를 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
일단 모든 가격을 내림했다고 가정하고 기본 오류(ret)를 누적합니다. 이때 각 가격의 오류는 소수 부분(x − low)입니다.
내림 대신 올림을 적용하면 합계가 정확히 1씩 증가하므로, 목표 값을 달성하기 위해 필요한 올림 횟수를 계산할 수 있습니다.
올림으로 전환할 때의 오류 변화량 diff = (high − x) − (x − low)를 최소 힙(min-heap) 형태의 우선순위 큐에 저장합니다.
필요한 만큼 diff가 가장 작은, 즉 오류를 가장 많이 줄여 주는 원소부터 꺼내 적용하면 전체 오류가 최소화됩니다.
구체적인 풀이 단계는 다음과 같습니다.
ret := 0으로 초기화합니다.
double 타입을 위한 우선순위 큐 pq를 생성합니다.
i를 0부터 prices의 크기까지 순회합니다.
x := prices[i]의 double 값
low := x의 내림값(floor)
high := x의 올림값(ceil)
low ≠ high인 경우, 즉 x가 정수가 아닌 경우:
diff := (high − x) − (x − low)
diff를 pq에 삽입
target := target − low
ret := ret + (x − low)
target이 pq의 크기보다 크거나 0보다 작으면 "-1"을 반환합니다.
target이 0이 될 때까지 다음을 반복합니다.
ret := ret + pq.top() 후 해당 원소를 pq에서 제거
target을 1씩 감소
s := ret을 문자열로 변환
소수점 셋째 자리까지만 잘라낸 부분 문자열을 반환합니다.
C++ 구현 예제
아래 구현 예제를 통해 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
struct Comparator{
bool operator()(double a, double b) {
return !(a < b);
}
};
class Solution {
public:
string minimizeError(vector<string>& prices, int target) {
double ret = 0;
priority_queue < double, vector < double >, Comparator > pq;
for(int i = 0; i < prices.size(); i++){
double x = stod(prices[i]);
double low = floor(x);
double high = ceil(x);
if(low != high){
double diff = ((high - x) - (x - low));
pq.push(diff);
}
target -= low;
ret += (x - low);
}
if(target > pq.size() || target < 0) return "-1";
while(target--){
ret += pq.top();
pq.pop();
}
string s = to_string (ret);
return s.substr (0, s.find_first_of ('.', 0) + 4);
}
};
main(){
vector<string> v = {"0.700","2.800","4.900"};
Solution ob;
cout << (ob.minimizeError(v, 8));
}
입력
["0.700","2.800","4.900"] 8
출력
"1.000"
동작 원리 분석
예제 입력에서 각 가격을 모두 내림하면 [0, 2, 4]가 되어 합계는 6입니다. 목표 값이 8이므로 두 개의 가격을 올림해야 하며, 이때 각 가격의 오류 변화량(diff)은 다음과 같습니다.
0.700 → 올림 시 diff = (1 − 0.7) − (0.7 − 0) = −0.4
2.800 → 올림 시 diff = (3 − 2.8) − (2.8 − 2) = −0.6
4.900 → 올림 시 diff = (5 − 4.9) − (4.9 − 4) = −0.8
모두 내림했을 때의 기본 오류는 0.7 + 0.8 + 0.9 = 2.4입니다. 여기서 diff가 가장 작은 두 개(−0.8, −0.6)를 선택해 올림으로 전환하면 2.4 − 0.8 − 0.6 = 1.000이 되어, 예상 출력과 정확히 일치함을 확인할 수 있습니다.
우선순위 큐를 사용하므로 이 알고리즘의 시간 복잡도는 O(n log n)입니다. 참고로 커스텀 비교자 Comparator가 !(a < b)를 반환하도록 정의되어 있어, 기본 max-heap과 반대로 동작하는 최소 힙이 구성된다는 점도 주목할 만합니다.