<Hard> Count of Smaller Numbers After Self (LeetCode : C#)

https://leetcode.com/problems/count-of-smaller-numbers-after-self/

📕 문제 설명

정수 배열 nums가 주어질 때 counts[i] 반환하기
counts[i] = nums[i] 기준 오른쪽으로 더 작은 숫자의 개수

• Input
  nums 배열
• Output
  현재 index기준 오른쪽에 더 작은 숫자의 개수를 담아서 반환

예제

시도 1.

완전 탐색 (Time Complexity : O(N^2)) + 같은거 패스해서 약간의 시간 챙기기..

public class Solution {
    public IList<int> CountSmaller(int[] nums) {
        int n = nums.Length;
        int[] minCount = new int[n];

        for (int i = n - 2; i >= 0; i--)
        {
            int currNum = nums[i];
            for (int j = i + 1; j < n; j++)
            {
                if (currNum == nums[j])
                {
                    minCount[i] += minCount[j];
                    break;
                }

                if (currNum > nums[j])
                {
                    minCount[i]++;
                }
            }
        }

        return minCount.ToList();  
    }
}

풀이

매 index별로 뒤에값들 담긴 정렬된 리스트에서 binary search 현재 값의 left index를 가져옴 (left index가 결국 자신보다 작은 것들의 개수를 나타내게 되므로!)

public class Solution {
    List<int> list = new List<int>();
    public IList<int> CountSmaller(int[] nums) {
        list.Add(nums[nums.Length-1]);
        nums[nums.Length-1]=0;
        for(int i = nums.Length - 2; i >= 0; i--) // 뒤에서부터 현재 index 값 구해주기
        {
            int sum = binSearch(nums[i]); // list에 현재 index기준 뒤에 값들 정렬된 상태로 담겨 있기에 binary search로 해당 값 찾기 (left index가 곧 자신보다 작은 것 개수임)
            nums[i] = sum;
        }
        return nums;
    }
    
    private int binSearch(int target)
    {
        int left = 0;
        int right = list.Count - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (list[mid] < target) left = mid + 1;
            else right = mid - 1;           
        }
        
        list.Insert(left, target);
        return left;
    }
}

결과

결과가 매우 좋지 않은데 ㅎ.. merge sort가 정석적 풀이다..!