118일 (2358. Maximum Number of Groups Entering a Competition) greedy

You are given a positive integer array grades which represents the grades of students in a university. You would like to enter all these students into a competition in ordered non-empty groups, such that the ordering meets the following conditions:

• The sum of the grades of students in the ith group is less than the sum of the grades of students in the (i + 1)th group, for all groups (except the last).
• The total number of students in the ith group is less than the total number of students in the (i + 1)th group, for all groups (except the last).

Return the maximum number of groups that can be formed.

 

Example 1:

Input: grades = [10,6,12,7,3,5]
Output: 3
Explanation: The following is a possible way to form 3 groups of students:
- 1st group has the students with grades = [12]. Sum of grades: 12. Student count: 1
- 2nd group has the students with grades = [6,7]. Sum of grades: 6 + 7 = 13. Student count: 2
- 3rd group has the students with grades = [10,3,5]. Sum of grades: 10 + 3 + 5 = 18. Student count: 3
It can be shown that it is not possible to form more than 3 groups.

Example 2:

Input: grades = [8,8]
Output: 1
Explanation: We can only form 1 group, since forming 2 groups would lead to an equal number of students in both groups.

 

Constraints:

• 1 <= grades.length <= 10^5
• 1 <= grades[i] <= 10^5

 

 

- 접근방법

 

현재그룹보다 다음 그룹이 학생 수가 더 많아야하며, 성적의 합도 더 높아야한다.

( ex) i그룹 1명, i+1그룹은 2명, i+2그룹은 최소 3명 성적의 합도 마찬가지로 i <  i+1 < i+2가 되어야함)

 

0. 성적이 음수가 아닌 이상에야 성적의 합은 함정이다.

 

- 모든 학생들의 성적이 같을 경우 : 그룹에 학생 수가 증가할 수록 성적의 합도 정확히  정비례하기 때문에 그룹의 학생 수만 고려하면 된다.

 

- 모든 학생들의 성적이 다를 경우 : 그룹에 학생 수를 증가시킬 때, 단지 성적이 낮은 학생부터 각 그룹에 추가한다면 그룹의 학생 수만 고려하면 된다.

 

 

1. 그러므로 결과적으로 학생 수만 고려하면 된다.

만약 grades.length가 6이라면 (1+2+3) 최대 3그룹을 리턴할 수 있다.

만약 grades.length가 10이라면 (1+2+3+4) 최대 4그룹을 리턴할 수 있다.

 

 

2. n(n+1)/2 는 1~n까지의 합을 나타내므로, n(n+1)/2 <= grades.legnth 의 조건을 만족하는 n의 최댓값을 리턴하면

최대 그룹의 수를 리턴하는 것과 같다.

 

 

- 코드

class Solution {
    public int maximumGroups(int[] grades) {
        int answer = 1;

        while((answer * (answer+1))/2 <= grades.length) { // 1, 2
           answer++;
        }

        return answer-1;
    }
}

 

처음에는 Arrays.sort(grades)를 하여 직접 오름차순 정렬 후 계산하였지만.

각 그룹에 학생을 추가하는 것과 점수를 추가하는 것은 생각으로 가정만 해도 되는 부분이라

마음 속에서 점수를 오름차순대로 학생들을 추가하였다. ㅋㅋ

 

 

 

 

https://leetcode.com/problems/maximum-number-of-groups-entering-a-competition/

LeetCode - The World's Leading Online Programming Learning Platform