[LeetCode/Kotlin]Medium - 2690. Happy Students

LeetCode - The World's Leading Online Programming Learning Platform

 

문제

You are given a 0-indexed integer array nums of length n where n is the total number of students in the class. The class teacher tries to select a group of students so that all the students remain happy.

The ith student will become happy if one of these two conditions is met:

• The student is selected and the total number of selected students is strictly greater than nums[i].
• The student is not selected and the total number of selected students is strictly less than nums[i].

Return the number of ways to select a group of students so that everyone remains happy.

Example 1:

Input: nums = [1,1]
Output: 2
Explanation:
The two possible ways are:
The class teacher selects no student.
The class teacher selects both students to form the group.
If the class teacher selects just one student to form a group then the both students will not be happy. Therefore, there are only two possible ways.

Example 2:

Input: nums = [6,0,3,3,6,7,2,7]
Output: 3
Explanation:
The three possible ways are:
The class teacher selects the student with index = 1 to form the group.
The class teacher selects the students with index = 1, 2, 3, 6 to form the group.
The class teacher selects all the students to form the group.

Constraints:

• 1 <= nums.length <= 105
• 0 <= nums[i] < nums.length

 

---

풀이

나의 풀이법

풀이 접근 과정

정렬을 접근하기까지가 어려웠다.

처음엔 dfs를 써야하나? dp를 써야하나? 고민이 많았다.

그러다가 정렬을 깨닫고 나서 문제가 풀렸다.

 

최종 소스코드

class Solution {
    fun countWays(nums: List<Int>): Int {
        var answer = 0

        val reverse = nums.sorted()

        reverse.forEachIndexed { idx, i ->
            if (idx == 0 && i != 0) answer++
            else if (idx >= i) {
                if (idx != nums.size-1) {
                    if (reverse[idx+1] > idx+1) answer++
                } else answer++
            }
        }

        return answer
    }
}

nums를 오름차순 정렬하여 reverse에 담는다.

현재 index가 0이지만 i 값이 0이 아니면 모두를 선택하지 않는 경우의 수가 생기므로 answer를 더해준다.

현재 index가 i 값보다 크거나 같은 경우,

   - i 값이 reverse의 마지막 값이 아니면, 내 다음 값이 학생수보다 큰 경우 answer를 더해준다.

   - i 값이 reverse의 마지막 값이면 answer를 더해준다.

그렇게 완성된 answer를 리턴한다.

 

 

---

Comment

정렬하는 것으로 접근하기까지는 어려웠는데 그 이후로는 꽤 간단히 풀렸다.

다만 조건을 설정해주는 것이 까다롭다고 느껴졌다.