[LeetCode] 315. Count of Smaller Numbers After Self

문제 URL : https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/

Count of Smaller Numbers After Self - LeetCode

문제 접근법: 

해당 배열이 주어질때  자기보다 작은숫자가 뒤에 몇개난 있는지 확인하는 문제입니다.

여러가지 접근이 가능합니다. 

그러나 저는 세그먼트 트리로 2가지 접근을 할수있는 방법을 설명해드리려고합니다.

 

첫번째 : nums[i]의 범위가 [-10000, 10000] 라서 1만을 더해 범위를 [0,20000]으로 바꿉니다.

count정렬이 가능하고 배열이 20001개를 사용할수있습니다.

그리고 nums를 거꾸로 바꿔 해당인덱스가 뒤를 보는게아니 앞을 보게 만들어 앞에

세그먼트트리로 0 부터  해당숫자 +10000 -1 까지의 합을 매번구하면

쉽게 답을 도출해낼수있습니다.

 

소스코드 : 

 

class Solution {
public:
vector<int> tree;
int n=20000;
int query(int l,int r,int s,int e,int node){
    if(l>e||r<s) return 0;
    if(l<=s&&e<=r)return tree[node];
    int mid =(s+e)>>1;
    return query(l,r,s,mid,node*2)+query(l,r,mid+1,e,node*2+1);
}
int query(int l,int r){
    return query(l,r,0,n,1);
}
void update(int val,int s,int e,int node){
    if(!(s<=val&&val<=e))return;
    if(s==e){
        tree[node]++;
        return;
    }
    int mid =(s+e)>>1;
    update(val,s,mid,node*2);
    update(val,mid+1,e,node*2+1);
    tree[node]=tree[node*2]+tree[node*2+1];
}
void update(int val){
    update(val,0,n,1);
}
vector<int> countSmaller(vector<int>& nums) {
    
    vector<int> res;
    tree=vector<int>(n*4+1);
    for(int i=nums.size()-1;i>=0;i--){
        res.push_back(query(0,nums[i]-1+n/2));
        update(nums[i]+n/2);
    }
    reverse(res.begin(),res.end());
    return res;
}
};

 

2번째 만약 nums의 범위가 int형 최소값에서 최대값까지 나온다면 절대 첫번째 방법을 사용할수없기때문에

nums의 범위에 구애 받지않고 풀수있는 방법을 고민했고

이것또한 세그먼트트리로 가능했습니다.

단 세그먼트트리 + 정렬을 이용해야 하며 

정렬후 해당인덱스가 몇번째였는지 확인하여 [idx,n-1]까지의 합에서 자기자신인 [idx,idx]의 합을 빼줘야합니다.

이유는 nums[i]의 중복된 숫자가 존재하기때문에 그것을 제외시키기위해 위함입니다.

 

소스코드: 

 

int n;
class Solution {
public:
vector<int> tree;
void update(int idx){
    for(tree[idx+=n]++;idx>1;idx>>=1){
        tree[idx>>1]=tree[idx]+tree[idx^1];
    }
}
int query(int l,int r){
    int res=0;
    for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
        if(l&1)res+=tree[l++];
        if(r&1)res+=tree[--r];
    }
    return res;
}
vector<int> countSmaller(vector<int>& nums) {
    vector<pair<int,int>> v;
    n=nums.size();
    tree=vector<int>(n*2);
    vector<int> res(n);
    for(int i=0;i<n;i++)v.push_back({nums[i],i});
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++){
        int idx = v[i].second;
        res[idx]=query(idx,n-1)-query(idx,idx);
        update(idx);
    }
    return res;
}
};

이번코드는 비재귀 세그먼트로 풀어봤습니다.

 

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.