LeetCode - The World's Leading Online Programming Learning Platform
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
문제
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
정렬하는 것으로 접근하기까지는 어려웠는데 그 이후로는 꽤 간단히 풀렸다.
다만 조건을 설정해주는 것이 까다롭다고 느껴졌다.
