[HackerRank]Fraudulent Activity Notifications(Sort) 풀이 Java

 

Fraudulent Activity Notifications | HackerRank

 

 

Sorting문제인데 어려웠음.. Counting Sort를 사용하지 않으면 풀 수 없는 문제이다.

나를 포함한 다수의 사람들이 기본 정렬을 사용했다가 Timeout이 발생했다.

 

Count sort는 아래 블로그에 굉장히 정리가 잘 되어 있으니 참고하면 좋다.

https://bowbowbow.tistory.com/8

Counting Sort : 계수 정렬

 

 

getMed(int d) : 문제에서 원하는 Median 값을 구하는 함수로 일반적인 Median 값에서 *2된 결과를 리턴함

Med 값을 구하는 것이 이 문제의 핵심이라고 할 수 있는데 홀수/짝수로 나눠서 진행한다.

 

특히, 홀수일때는 조건에 = 가 들어가지 않지만 짝수일때는 조건이 >=로 진행된다.

if (d % 2 != 0) {
	if (sum > idx)
		return i * 2;
} else {
	if (sum >= idx && tmp == 0)
		tmp = i;
	if (sum >= idx + 1) {
		tmp += i;
		break;
	}
}

 

예) expenditure={2,3,4,2,3,6,8}

풀이에서는 sum을 배열로 저장하지 않았지만, 위 블로그에서 count sort를 보고 왔다면 아래 sum 배열을 이해할 수 있다.

idx	1	2	3	4	5	6	7	8
val		2	4	5		6		7

d=5 (홀수) 일 때, 5/2=2 이다.

정렬된 배열은 {2,2,3,3,4} 라서 med는 3이 되어야 한다.

하지만 위 표를 보고 >= 조건으로 idx를 찾으면 숫자 2가 나온다.

따라서 홀수일 때는 = 조건을 사용하지 않는다.

 

짝수일 때 사용하는 이유는 d=6(짝수)로 동일하게 예시를 만들어서 하면 이해가 가능하다.

 

마지막으로

0<=expenditure[i]<=200 조건때문에 이 문제는 counting sort를 사용하면 좋다.

그 이유는 counting sort는 정렬하는 숫자가 특정한 범위(0~200) 안에 있을 때 사용하기 때문이다.

이유를 생각해보면 만약 0~1억 이라는 범위가 있으면 count 배열의 사이즈를 1억으로 잡아야 하기 때문에 메모리 낭비가 굉장히 크다.

 

그리고 expenditure의 조건에 0이 포함된 것을 다시 한번 확인하자. (getMed에서 for문이 0부터 시작하는 이유)

class Result {
    static int[] count = new int[201];

    public static int getMed(int d) {

        int tmp = 0;
        int idx = d / 2;
        int sum = 0;

        for (int i = 0; i < 201; i++) {
            sum += count[i];

            if (d % 2 != 0) {
                if (sum > idx)
                    return i * 2;
            } else {
                if (sum >= idx && tmp == 0)
                    tmp = i;

                if (sum >= idx + 1) {
                    tmp += i;
                    break;
                }
            }
        }

        return tmp;
    }
    public static int activityNotifications(List<Integer> expenditure, int d) {
        // Write your code here

        int res = 0;

        for (int i = 0; i < d; i++) {
            count[expenditure.get(i)]++;
        }

        for (int i = d; i < expenditure.size(); i++) {

            int m = getMed(d);

            int val = expenditure.get(i);

            if (val >= m)
                res++;

            count[val]++;
            count[expenditure.get(i - d)]--;

        }
        return res;
    }
}