2028. Find Missing Observations

https://leetcode.com/problems/find-missing-observations/

난이도 : medium

문제

주사위를 굴렸을 때 굴린 주사위 수의 총합의 평균값을 mean과 같게 만드는 문제이다. mean 은 평균값을 의미하고 n 아직 던지지 않은 주사위 횟수이다.

 

예시를 확인 해보면

입력: 롤 = [3,2,4,3], 평균 = 4, n = 2

현재까지 주사위를 굴린 값은 [3, 2, 4, 3]이며 평균은 4, n 은 2이다.

n회 주사위를 굴려서 주사위의 총합의 평균을 4로 만드는 수를 찾아야 한다. 예시에 답은 [6,6]이다.

모든 n + m 롤의 평균은 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4. // 즉 3 2 4 3번 입력에서 주어지는 값이며, N 만큼 주사위를 굴려서 전체 평균이 4 가되는 수를 찾으면 된다.

 

소스코드

필자의 코드는 아래와 같다. 그리드 하게 접근했는데 코드가 더럽다 다시 봐도 헷갈린다;

class Solution {
public:
    vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
        
        int fSum = 0;
        for(auto a:rolls) fSum += a;
        
        int fSize = rolls.size() + n;
        
        // 총 구해야하는 값
        int calculatedSum = mean * fSize;
        cout << "총구해야하는 값 " << calculatedSum << endl;
        
        if (calculatedSum > (fSum + (n * 6)))
            return {};
        
        cout << fSum << endl;
        
        int remainedSum = calculatedSum - fSum;
        cout << "구해야하는 값"  << remainedSum << endl;
        if (remainedSum < 0) {
            return {};
        }
         
        int meanCount = remainedSum / n;
        
        cout << "평균값 " << meanCount << endl;
        if (meanCount >=7 || meanCount == 0) {
            return {};
        }
        
        vector<int> arr;
        for(int i = 0; i<n; i ++) {
            remainedSum -= meanCount;
            arr.push_back(meanCount);
        }
        
        while(remainedSum) {
            
            for(int i = 0 ; i < arr.size(); i ++) {
                if (arr[i] < 6) {
                    arr[i]++;
                    remainedSum--;
                }
                if(remainedSum == 0)
                    break;
            }
        }
        return arr;
    }
};

 

Most Votes 코드 확인

missingSum을 계산하기 위해 약간의 수학이 필요합니다 n + m 롤의 평균값 은 정확히 mean  값입니다. 

curSum = sum(rolls)
(curSum + missingSum) / (n + m) == mean
curSum + missingSum = mean * (n+m)
missingSum = mean * (n+m) - curSum

Now, we just need to distribute missingSum into n roll dices, each roll dices must have values in range [1.. 6].

class Solution {
public:
    vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
        int curSum = accumulate(rolls.begin(), rolls.end(), 0), m = rolls.size();
        int missingSum = mean * (n + m) - curSum;
        if (missingSum < n || missingSum > 6*n) return {};
        
        int part = missingSum / n, rem = missingSum % n;
        vector<int> ans(n, part);
        for (int i = 0; i < rem; ++i) 
            ++ans[i];
        return ans;
    }
};

missingSum을 구해서 주사위를 굴렸을대 범위 체크를 하고 missingSum / n을 통해 구해야할 원소의 평균값을 삽입 rem = missingSum % n 을 통하여 나머지 값이 있으면 값을 채워주는 식으로 접근하였다.