해설
- 평균은 정수 나눗셈으로 구합니다. 평균이 M보다 크면 −1을 출력합니다.
- 평균이 M 이하이면, 평균 이하로 멘션을 보낸 사람은 멘션이 M번 이하라서 메시지가 겹치지 않습니다.
- 1번 메시지는 모든 사람에게 가므로 N번 보냅니다.
- i번 메시지(i≥2)는 멘션 횟수가 i 이상이고 평균 이하인 사람에게 한 번씩 갑니다.
- 멘션 횟수가 평균 이하인 사람을 횟수별로 센 뒤, M부터 거꾸로 누적합을 구하면 i번 이상 보낸 사람 수가 나옵니다.
- 사람을 한 번 훑는 데 O(N), 누적합에 O(M)이 들어 시간복잡도는 O(N+M)입니다.
- 정렬한 뒤 이분탐색을 써도 됩니다.
- 2번 이상 멘션을 보낸 사람의 수를 이분탐색 1번으로 구합니다.
- 평균이 정렬된 배열의 어디에 오는지 이분탐색 1번으로 찾습니다.
- i번 이상 멘션을 보낸 사람 중 평균 이하인 사람의 수를 i마다 이분탐색으로 구합니다(M번).
- 이 풀이의 시간복잡도는 입니다.
O((N+M)logN)
