1365-kir3i.md

1365. How Many Numbers Are Smaller Than the Current Number

Solution

• 시간복잡도: O(NlogN)

• 알고리즘

  구현, 자료구조

• 풀이설명

  주어진 nums를 정렬하면 각 요소보다 작은 값의 수는 인덱스 값과 같습니다. 그러나 이렇게만 구현하면 중복값이 있을 때 문제가 될 수 있는데 중복되는 값에 대해선 제일 첫번째 값의 인덱스값만 저장하게 구현하면 해결됩니다. 각 원소보다 작은 값의 수는 cnt에 저장했고 자료구조로는 Hash map을 이용했습니다.

• 소스코드

  • C++

    class Solution {
    public:
        vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
            unordered_map<int, int> cnt;
            vector<int> t = nums;
            sort(t.begin(), t.end());
            for(int i=0; i<t.size(); i++)
                if(!cnt.count(t[i]))
                    cnt[t[i]] = i;
            
            vector<int> ans;
            for(const int &x: nums)
                ans.push_back(cnt[x]);
            return ans;
        }
    };

  • Python

    class Solution:
        def smallerNumbersThanCurrent(self, nums):
            cnt = {}
            for i, x in enumerate(sorted(nums)):
                if x not in cnt:
                    cnt[x] = i
    
            return [cnt[x] for x in nums]

  • Java

    class Solution {
        public int[] smallerNumbersThanCurrent(int[] nums) {
            HashMap<Integer, Integer> cnt = new HashMap<Integer, Integer>();
            int[] t = Arrays.copyOf(nums, nums.length);
            Arrays.sort(t);
            for(int i=0; i<t.length; i++)
                if(!cnt.containsKey(t[i]))
                    cnt.put(t[i], i);
            
            int[] ans = new int[nums.length];
            for(int i=0; i<nums.length; i++)
                ans[i] = cnt.get(nums[i]);
            return ans;
        }
    }