[C++] HackerRank 해커랭크 Fraudulent Activity Notifications 풀이

Counting sort를 몰라서 어려웠던 문제...

시작 전에

https://bowbowbow.tistory.com/8

Counting Sort : 계수 정렬

 

이 블로그 글을 참조하시면 좋습니다. 

 

---

문제의 조건

1. 은행에서 기준이 되는 추적 범위 날짜(trailing days)들의 중위값을 선정해서 추적 범위 날짜 이후에 쓴 돈이 (중위값 * 2)보다 크거나 같으면 알림을 보낸다. 

2. 주어진 배열의 길이만큼의 날짜가 끝났을 때 고객이 받을 알림의 갯수를 구하기 

3. 단 추적 범위 날짜가 홀수면 중위값을 하나 뽑아서 * 2 하면 되는데, 

짝수라면 중위값 2개의 평균값 * 2이다. 

-> 즉 짝수일 땐 중위값 2개의 합을 구하면 된다. 

 

---

이 문제 또한 시간제한이 있기 때문에 정렬을 위한 배열 순회를 최대한 줄이는 것이 좋습니다. 

 

예를 들면 처음에 생각할 수 있는 방법은 원본 배열에서 traling days만큼 새로운 배열에 복사한 다음 새 배열을 오름차순으로 정렬한 다음 중위값을 구하기 위해 접근하는 것이 있습니다. (네 제가 거쳤던 과정...)

그런데 알고리즘의 sort를 써도 저기에서 타임아웃이 걸리더라고용...

그래서 이 방법은 버리고

 

일정 범위 내의 숫자를 정렬할 땐 속도가 빠른 Counting sort를 이용하기로 했습니다. 

Discussions에서 많은 사람들이 Counting sort로 풀었길래 저도 Counting sort에 대해 공부한 후 도전했습니다. 

 

#define MAX_NUM 200 //문제의 조건 중 배열의 요소가 가질 수 있는 최대값

//중위값*2를 구하기 위한 함수 
int GetDoubleMedian(vector<int> &vecCount, int d)
{
    //trailing days로 선정된 숫자들의 counting 누적합계를 구하기 위한 배열
    //첨부한 블로그 글을 보고 오시면 이해가 빠릅니다. 
    vector<int> vecCountSum(vecCount);
    
    //누적합계를 구한다. 
    //다음 인덱스에 합계가 누적 되어야 하기 때문에 1번째 인덱스부터 시작 
    for (int i = 1; vecCountSum.size() > i; i++)
        vecCountSum[i] += vecCountSum[i - 1];
    
    int iMedian;
    int a = 0, b = 0;
    
    //d(trailing days)가 짝수인 경우 중위값 2개를 구해야 한다. 
    //두개를 더한 값의 평균의 2배는 합과 같으니까 두 수의 합을 구한다. 
    if (0 == d % 2)
    {
        //예를 들어 d=[2,3,5,3,2]일 때 
        //counting sort는 해당 숫자가 원본 배열에 몇 개나 들어있는지 세어서 
        //센 값을 해당 숫자와 일치하는 인덱스의 요소로 저장한 후 그 값을 기준으로 정렬하는 방식임
        //그래서 count 배열에는 [0,0,2,2,0,1]식으로 같은 숫자가 반복되는 횟수가 저장된다. 
        //그렇기 때문에 일반적인 배열 인덱스 접근방식이 아닌 보이는 숫자 그대로 인덱스에 접근하면 됨
        
        //첫번째 중위값을 찾을 피봇 
        //d=[1,2,3,4]면 2
        int iFirst = d * 0.5f;
        //두번째 중위값은 첫번째의 다음 순서가 될 것임 
        //예시에선 3
        int iSecond = iFirst + 1;
        int i = 0; //반복문을 이어서 두 번 돌아야해서 반복문 밖에서 선언 
        
        //예시의 count 배열은 [0,1,1,1,1]
        //count 배열의 누적합계 배열은 [0,1,2,3,4]
        for (; vecCountSum.size() > i; i++)
        {
            //그렇기 때문에 2보다 작거나 같은 조건이면 1은 거르고 2에서 멈출 수 있다. 
            if (vecCountSum[i] >= iFirst)
            {
                a = i;
                break;
            }
        }
        
        //실제 테스트를 진행하면 모든 수가 항상 연속으로 나열되어있진 않다. 
        //첫번째 중위값과 두번째 중위값 사이의 간격이 두 칸 이상일 수 있기 때문에 반복문으로 한 번 더 탐색
        for (; vecCountSum.size() > i; i++)
        {
            if (vecCountSum[i] >= iSecond)
            {
                b = i; 
                break;
            }
        }
    }
    else //d=홀수인 경우 
    {
        int iFirst = d * 0.5f + 1;
        
        for (int i = 0; vecCountSum.size() > i; i++)
        {
            if (vecCountSum[i] >= iFirst)
            {
                a = i * 2;//하나 뽑은 중위값을 2배 시켜주면 됨 
                break;
            }
        }
    }
        
    iMedian = a + b;
    
    return iMedian;
}

int activityNotifications(vector<int>& expenditure, int d) {
    
    int iCount = 0; //고객 알림 횟수 저장 
    
    //couning sort는 저장된 수와 같은 인덱스에 카운트 수를 저장하는데 
    //만약 숫자 범위가 1~10이라 MAX_NUM=10 일 때 10만큼만 배열 크기를 할당하면 인덱스 번호는 9에서 끝남
    //-> 10의 반복 횟수를 저장하려면 10번째 인덱스에 접근해야 하는데 접근 불가
    //-> 인덱스 에러 남 
    //마지막 요소에 접근할 수 있게 +1
    vector<int> vecCount(MAX_NUM + 1);
    
    //반복되는 횟수 세기 
    //첫날부터~d번째 날짜까지는 정보 수집 기간이라 알림을 안 보냄
    //첫번째 정보 수집을 위한 반복문 
    for (int i = 0; d > i; i++)
        vecCount[expenditure[i]]++;
    
    //첫번째 정보 수집 기간이 끝나는 다음날부터 소비 확인하고 알림을 보내야 함 
    for (int i = d; expenditure.size() > i; i++)
    {
        //위에서 썼던 함수로 *2된 중위값을 구한다. 
        int iMedian = GetDoubleMedian(vecCount, d);
        
        //만약 *2된 중위값보다 같거나 많이 썼으면 알림 전송 
        if (iMedian <= expenditure[i])
            iCount++;
        
        //정보 수집 기간이 한 칸 앞으로 전진하고 그만큼 뒤에는 줄어든다. 
        //크기가 정해져있는 queue가 전진한다고 생각하면 됨 
        //새롭게 추가될 날은 횟수 추가하고 지워질 날은 횟수 감소 
        vecCount[expenditure[i]]++;
        vecCount[expenditure[i - d]]--;
    }
    
    return iCount;
}

 

최대한 이해하기 쉽게 주석을 달아보았습니다. 

많은 도움이 되길 바라며...

 

이번 문제를 통해 깨달은 것: 세상엔 정렬 방법이 정말 많다.