Fraudulent Activity Notifications

🔗 문제 링크

https://www.hackerrank.com/challenges/fraudulent-activity-notifications/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=sorting

❔ 문제 설명

HackerLand National Bank has a simple policy for warning clients about possible fraudulent account activity. If the amount spent by a client on a particular day is greater than or equal to the client's median spending for a trailing number of days, they send the client a notification about potential fraud. The bank doesn't send the client any notifications until they have at least that trailing number of prior days' transaction data.

Given the number of trailing days and a client's total daily expenditures for a period of days, determine the number of times the client will receive a notification over all days.

Example

expenditure = [10,20,30,40,50]
d = 3

On the first three days, they just collect spending data. At day 4, trailing expenditures are [10,20,30]. The median is 20 and the day's expenditure is 40. Because 40 ≥ 2 x 20, there will be a notice. The next day, trailing expenditures are [20,30,40] and the expenditures are 50. This is less than 2 x 30 so no notice will be sent. Over the period, there was one notice sent.

Note: The median of a list of numbers can be found by first sorting the numbers ascending. If there is an odd number of values, the middle one is picked. If there is an even number of values, the median is then defined to be the average of the two middle values. (Wikipedia)

Function Description

Complete the function activityNotifications in the editor below.

activityNotifications has the following parameter(s):

• int expenditure[n]: daily expenditures

• int d: the lookback days for median spending

Returns

• int: the number of notices sent

Input Format

The first line contains two space-separated integers n and d, the number of days of transaction data, and the number of trailing days' data used to calculate median spending respectively.
The second line contains n space-separated non-negative integers where each integer i denotes expenditure[i].

⚠️ 제한사항

• $1 ≤ n ≤ 2 × 10^5$

• $1 ≤ d ≤ n$

• $0 ≤ expenditure[i] ≤ 200$

---

💡 풀이 (언어 : Java)

또다시 시간복잡도에서 걸려 풀이에 실패했다. 타인의 풀이를 공부했다. 나와 다른점은 int 배열을 원소의 최대 크기 만큼 (201) 선언해 거기에 원배열의 값인 인덱스 부분에 1 표시해주고 이를 중위수 인덱스가 될때까지 계속 더해주고 그 인덱스를 사용한다. 그리고 배열에서 최근 값의 인덱스 부분을 +1 해주고 거기서 간격만큼 앞에있는 인덱스를 -1해줬다. 이건 어려운 문제였다ㅠ

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    private static double CalMedian(int[] medianArr, int d, boolean isOdd) {
        double median = 0;
        int idx = 0;

        if (isOdd) {
            for (int i = 0; i < medianArr.length; i++) {
                idx += medianArr[i];
                if (idx > d / 2) {
                    median = i;
                    break;
                }
            }
        } else {
            int first = 0;
            int second = 0;

            for (int i = 0; i < medianArr.length; i++) {
                idx += medianArr[i];
                if (first == 0 && idx >= d / 2) {
                    first = i;
                }
                if (second == 0 && idx >= d / 2 + 1) {
                    second = i;
                    break;
                }
            }
            median = (first + second) / 2.0;
        }
        return median * 2;
    }

    private static int activityNotifications(int n, int d, int[] data) {
        int count = 0;
        int[] medianArr = new int[201];
        boolean isOdd = (d % 2 == 0) ? false : true;

        for (int i = 0; i < d; i++) {
            medianArr[data[i]]++;
        }

        for (int i = d; i < n; i++) {
            double median = CalMedian(medianArr, d, isOdd);
            if (median <= data[i]) {
                count++;
            }
            medianArr[data[i]]++;
            medianArr[data[i - d]]--;
        }
        return count;

    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int d = Integer.parseInt(st.nextToken());
        int[] data = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        System.out.println(activityNotifications(n, d, data));
        br.close();
    }
}