HackerRank : Fraudulent Activity Notifications

문제 링크

HackerRank : Fraudulent Activity Notifications (Click)

문제 요약

1. List<integer> 타입의 expenditure와 int타입의 d가 아래와 같이 주어진다.
2. expenditure = [10,20,30,40,50] d = 3
3. 중간값의 정의는 해당 글을 참고한다.
4. 예를 들어 위와 같이 d가 3인 경우, n-3, n-2, n-1의 값중 중간값 * 2 이상의 값을 n번째 날이 가질 경우, 고객에게 알림을 보내줘야한다.
5. 10,20,30의 중간값은 20인데, 40의 경우 20*2 이상의 값을 가지므로 알림을 보내야한다.
6. 20,30,40의 중간값은 30인데, 50의 경우 30*2 보다 값이 작으므로 알림을 보낼 필요가 없다.
7. 때문에 위 예시에서 알림을 보내는 개수(정답)는 1이 된다.

문제 풀이

문제에서 언급된 아래의 제약 사항을 잘 확인해야 한다.

0 <= expenditure[i] <= 200

1일당 금액은 아무리 커도 0 ~ 200 사이인데, 이런 경우엔 계수정렬을 활용하는게 좋다.
(계수정렬 참고 : https://astrid-dm.tistory.com/48)
무턱대고 라이브러리에서 제공하는 기본 sort를 사용할 경우, 시간초과가 나기 딱 좋기 때문이다.

    public static int activityNotifications(List<Integer> expenditure, int d) {
    // Write your code here
        int left = 0, right=d-1, ans = 0, mid = 0;
        int[] temp = new int[201];
        for(int i=0; i<d; i++) temp[expenditure.get(i)]++;

        while(right < expenditure.size()-1){ // 윈도우 슬라이싱 (Windoe Slicing) 활용
            mid = findMid(temp,d);
            if(expenditure.get(right+1) >= mid) ans++;
            temp[expenditure.get(left)]--;
            left++;
            right++;
            temp[expenditure.get(right)]++;
        }
        return ans;
    }

    public static int findMid(int[] arr, int d) {
        int temp = 0;
        int idx = 0;
        int point = d/2;
        for(int i=0; i<arr.length; i++){
            if(arr[i] != 0) idx += arr[i];
            if(d%2 != 0){
                if(idx > point){ // d가 홀수인 경우
                    return i*2;
                }
            } else { // d가 짝수인 경우
                if(idx >= point && temp == 0) {
                    temp = i;
                }
                if(idx >= point+1) {
                    temp += i;
                    break;
                }
            }
        }
        return temp;
    }

d가 짝수인 경우만 주의하면 되는데, 저렇게 짝수인 경우에만 케이스가 나뉘는 이유는 아래의 예시에서 설명될 수 있다.

case 1 : {1,2,2,3,3,3,   5} -> 가운데 2,3을 가져가야함
case 2 : {1,2,2,3,3,3,3,3,    7} -> 가운데 3,3,을 가져가야함

시간복잡도

O(n * 201)