오늘의 커밋. 알고리즘 문제풀이

---

오늘은 해커랭크에서 알고리즘 문제를 풀었습니다.

퇴근하면서 문제를 풀 방법을 떠올리고, 집에와서 완성했는데

예상 외로 시간제한이 걸려버렸네요.

---

오늘은 집에서 도무지 공부가 안되는것 같아

 

딱히 할일이 없는데도 불구하고 회사에 남아 야근을 했습니다.

 

결국 회사에서는 알고리즘 문제풀이(해석) 정도밖에 하지못했지만요.

 

알고리즘 문제를 풀면서 항상 생각하지만은

 

코딩테스트를 통과하기에 제 손은 너무나 느린 것 같아요

 

어떻게든 문제는 풀겠는데

 

몇일에 걸쳐, 몇시간에 걸쳐 간신히 푸는정도입니다.

(답을 몰라서가 아니라 완벽하게 모든 테스트케이스를 통과하지 못하는 반쪽짜리 답을 내고,

이후에 하나하나 맞춰가기 때문에 느립니다.)

 

이래서 어떤 기업이든 코딩테스트를 보면 제대로 통과는 할 수 있을지 걱정이 되기도 하네요.

 

 

여튼, 오늘은 해커랭크의

Fraudulent Activity Notifications

 

라는 문제를 풀었습니다.

 

문제 컨셉은 사용자의 소비 패턴을 분석하여 한번에 평소보다 많은 돈을 인출하면 경고 알림을 띄우는 것입니다.

 

사용자는 기준이 될 소비기간을 정할 수 있고, 일별 지출 내역이 배열로 주어집니다.

 

예를들어

월 화 수 목 금에

 

10 20 30 40 50 원을 썼고, 3일을 기준으로 한다면

 

기준이 되는것은

10 20 30

20 30 40

30 40 50 이 되는 것입니다.

 

해당 기간동안의 중위값을 구하는것이 이 문제의 핵심입니다.

 

중위값은 배열을 정렬하고 (배열의 길이 / 2) 번째 값이죠.

 

범위가

 

이정도니 당연히 모든 배열을 정렬해서 풀 수는 없습니다.

 

한참을 고민하다 인터넷에서 200개! 라는 힌트를 보고 답을 찾았죠

 

해쉬맵입니다.

 

이런식으로 배열을 해쉬에 저장하고, 1부터 200까지 돌면서 각각의 인덱스에 접근합니다.

 

sArr[1] ~ sArr[200] 이니까

 

정렬을 하지 않아도 무조건 아래에서 위로 탐색할 수 있습니다.

 

또, 각각의 숫자가 카운트 되어있기 때문에

 

숫자가 존재할때마다 카운트하고, 중위값과 동일해지는 순간 해당 위치의 값이 중위값이 되는것이죠.

설명하기에는 좀 어렵긴 하네요

 

 

여튼 제가 생각한 답은 저것이었는데

 

결론적으로 틀렸습니다.

 

시간제한이 걸리네요

 

내일 한번 이 문제를 다시 보도록 합시다