[LeetCode] 2028. Find Missing Observations

https://leetcode.com/problems/find-missing-observations/description/?envType=daily-question&envId=2024-09-05

leetcode - Find Missing Observations

문제 유형 : 구현, 수학

문제 난이도 : Medium

 

문제

You have observations of n + m 6-sided dice rolls with each face numbered from 1 to 6. n of the observations went missing, and you only have the observations of m rolls. Fortunately, you have also calculated the average value of the n + m rolls.

You are given an integer array rolls of length m where rolls[i] is the value of the ith observation. You are also given the two integers mean and n.

Return an array of length n containing the missing observations such that the average value of the n + m rolls is exactly mean. If there are multiple valid answers, return any of them. If no such array exists, return an empty array.

The average value of a set of k numbers is the sum of the numbers divided by k.

Note that mean is an integer, so the sum of the n + m rolls should be divisible by n + m.

 

당신은 주사위를 n + m번 굴린다. 이미 m번 굴렸는데, 그 결과는 이미 rolls에 담겨있다.

나머지 n번을 굴려서 총 평균을 mean이되는 굴린 주사위의 경우의 수를 구하시오.

여러 가지 경우의수가 있을 수 있는데, 하나라도 상관없고, 하나라도 없는 경우면 빈 배열을 반환하시오.

 

풀이

goal = (n+m) * mean 은 우리가 구해야 하는 총합이 된다.

 

이미 m번 굴린 수들에 대해서, goal에서 빼주자.

남은 goal의 수가 n보다 작거나 6*n보다 크면, 빈 배열을 반환한다. (모두 1씩줘도 안됨, 모두6씩줘도 안됨)

 

길이가 n인 배열을 만든다.

goal / n만큼 값을 할당하고, 나머지수를 1씩 배열에 할당해준다.

 

ex) 남은 수가 11, n = 3이면,

처음에 [3, 3, 3]할당. 남은 수는 2.

인덱스0과 1에 1씩 준다.

값은 [4, 4, 3]

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<int> missingRolls(vector<int>& rolls, int mean, int n) {
        int sum = 0;
        int m = rolls.size();
        for(int roll : rolls) {
            sum += roll;
        }

        int goal = (m + n) * mean;
        int left = goal - sum;

        if(left > 6 * n || left < n) return {};

        vector<int> ans (n, left / n);
        left %= n;

        for(int i = 0; left > 0; i++) {
            ans[i]++;
            left--;
        }

        return ans;
    }
};

 

 

Go

func missingRolls(rolls []int, mean int, n int) []int {
    m := len(rolls)
    goal := (m + n) * mean

    for _, v := range rolls {
        goal -= v
    }

    if goal < n || goal > 6 * n {
        return make([]int,0)
    }

    ans := make([]int, n, n)
    i := 0
    for i < goal % n {
        ans[i] = (goal / n) + 1
        i++
    }

    for i < n {
        ans[i] = (goal / n)
        i++
    }

    return ans
}