[PS]#Fraudulent Activity Notifications

 

---

 

 

https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem?isFullScreen=true

Fraudulent Activity Notifications | HackerRank

 

#include <bits/stdc++.h> 
using namespace std; 
vector<int> vec; 
int n, answer;

int FindLoca(int s, int e, int val) 
{ 
    int mid = (s + e) / 2; 
    if (e <= s) return mid; 
    if (vec[mid] >= val) return FindLoca(s, mid, val); 
    else if (vec[mid] < val) return FindLoca(mid + 1, e, val); 
    return mid; 
}

void PushAndSort(int delVal, int pushVal) 
{ 
    int delLocat = FindLoca(0, vec.size() - 1, delVal); 
    vec.erase(vec.begin() + delLocat); 
    int inLocat = FindLoca(0, vec.size() - 1, pushVal); 
    if (inLocat == vec.size() - 1 && vec[inLocat] < pushVal) 
    { 
        vec.push_back(pushVal); 
        return; 
    } 
    vec.insert(vec.begin() + inLocat, pushVal); 
}

int solution(vector<int> expenditure, int d) 
{ 
    n = expenditure.size(), answer = 0; 
    if (n <= d) return 0; 
    int idx = d; 
    for (int i = 0; i < d; ++i) vec.push_back(expenditure[i]); 
    sort(vec.begin(), vec.end()); 
    while (1) 
    { 
        if (d % 2 == 1) 
        { 
            if ((vec[d / 2]) * 2 <= expenditure[idx]) ++answer; 
        } 
        else if (d % 2 == 0) 
        { 
            double dd = (vec[d / 2 - 1] + vec[d / 2]) / 2.0; 
            if (dd * 2.0 <= static_cast<double>(expenditure[idx])) ++answer; 
        } 
        if (idx + 1 >= n) break; 
        PushAndSort(expenditure[idx - d], expenditure[idx]); 
        ++idx; 
    } 
    return answer; 
}

 

* 문제 풀이 과정

 

1. d 만큼 vec 추가 후 정렬.

2. d 의 짝수, 홀수 분간 후 문제의 방식대로 계산.

3. 계산 후, vec size 를 유지하며 분할 정복으로 이전 처음의 값을 찾아 지운다.

4. 마찬가지로 분할 정복으로 정렬될 위치를 찾고 삽입.

5. 끝 원소까지 반복.

 

정렬로 인한 시간 복잡도를 어떻게 줄일 수 있느냐가 핵심인 문제였다.

위치 검색 log(n) 을 구현하기 위해 분할 정복을 사용했다.

 

 

 

* 해결 과정 문제점

분할 정복 순서, 계산 방식 순서, 함수 호출 매개변수 ++idx 문제

 

 

 

* 또 다른 해결 방법

카운팅 정렬

 

 

 

---