[LeetCode] - How Many Numbers Are Smaller Than the Current Number

        brute force => 500 ^ 500 => 25000 성능상으로 느리진 않을거 같긴함
        brute force 말고
        위치기억
        sorting?
        순회하면서 나머지 비교 selection sort
        생각을 해봅시다
        주어진 nums배열을 두고
        배열을 복사한다. space complexity O(N)
        복사한 배열을 sorting time complexity O(N) X => tim sort -> O(n log n)
        Map<Integer, Integer> key는 
        음 계수정렬을 써볼까 어짜피 0 ~ 100 공간만 있으면 됌

import java.util.*;

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
       
        int numsCount = nums.length;
        int[] countingArr = new int[101];  // space complexity O(M)
        // time complexity O(N)
        for(int temp : nums){
            countingArr[temp]++;
        }
        
        // O(M)
        for(int idx = 100; idx >= 0; idx--){
            if(countingArr[idx] > 0) {
                numsCount = numsCount - countingArr[idx];
                countingArr[idx] = numsCount;
            }
        }
        
        // O(N)
        for(int idx = 0; idx < nums.length; idx++){
            int temp = countingArr[nums[idx]];
            nums[idx] = temp;
        }
        
        return nums;
        
    }
}

// time Complexity -> O(N+N)
// space Complexity -> O(M)
Runtime: 1 ms, faster than 97.51% of Java online submissions for How Many Numbers Are Smaller Than the Current Number.
Memory Usage: 39.1 MB, less than 55.96% of Java online submissions for How Many Numbers Are Smaller Than the Current Number.