[leetcode] 2028. Find Missing Observations

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

---

 

1~6까지 수가 새겨진 주사위가 (n+m)개가 있다.

모든 주사위를 굴린 값들 중 m개 주사위에 대한 정보를 가지고 있고 (n + m)개의 주사위의 평균값 mean 값도 알고 있다고 할 때, 가능한 n개의 주사위 결과를 반환하라. 만일 가능한 정답이 없다면 빈 배열을 반환하라.

---

mean 값에 (n + m)을 곱하면 모든 주사위 값들을 더한 값이 된다.

이 값에 입력값으로 주어진 m개 주사위들의 값들을 뺀다면 n개의 주사위 눈들의 합(let, sum)이 된다.

sum = mean * (n+m) - m개의 주사위 눈들의 합 = n개의 주사위 눈들의 합

sum / n 을 초기화 값으로 n 배열을 만들고 sum % n 개의 배열 값들은 +1 해주면 정답이 된다.

이렇게 정답 배열들을 채워나갈 때 값이 1이상 6이하가 아니면 조건에서 벗어나므로 정답 가능한 경우가 없어서 빈 값을 반환한다.

 

ex) rolls = [1,5,6], mean = 3, n = 4.

sum = 3 * (3+4) - (1+5+6) = 21 - 12 = 9

9/4 = 2 => [2,2,2,2] (초기값이 2인 크기가 4인 배열)

9%4 = 1 => [3,2,2,2] (1개 값에 +1)

 

시간복잡도는 O(n + m).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/medium/2028.%20Find%20Missing%20Observations.cpp