[알고스팟] RUNNING MEDIAN

junwoo4690·2018년 12월 31일
0
post-thumbnail

최근 취업 준비를 하면서 알고리즘 문제를 공부할 필요성을 느껴서 문제를 풀어보고 있다. 몇몇 문제는 내가 상상조차 불가능해서 손도 못대는 경우도 있지만...
일단 노력해보고 있다...허허
너무 간단히 푼 문제말고, 어렵게 느껴졌던 문제나...
새롭게 알게된 경우는 블로그에 풀이?를 올려서 나중에 다시 볼 수 있도록 올려볼 생각이다.

오늘 푼 문제는...

문제

알고스팟 RUNNING MEDIAN

~~ 자세한 입력과 출력 및 문제를 풀어보실 분은 위 주소로 가시면 푸실 수 있습니다. ~~

문제를 처음보고 '아 , 정렬해서 가운데 값 보내주면 되겠구나! 간단하네!' 하고

이렇게 풀었었다.....

당연히 결과는 >>>

시간초과였다....허허

이 후에 알고보니 이 문제는 보통은 2개의 Heap으로 구성해서 한 쪽에는 작은 숫자, 한쪽에는 큰 숫자들을 넣고, 이를 중간중간에 Heap의 원소가 한쪽이 더 커지지 않도록 하는 방법을 이용해서 많이 푼다는 것을 알게 되었다.

그래서 이번에는 구글의 도움으로 아래와 같이 Heap을 이용하여 문제를 풀어보았다.

결과는.................

통과!

비록 온전히 내 머리로만 푼 건 아니지만 정답글자를 보는 건 언제나 기분이 좋은 듯하다.

이 코드를 보면

  1. lowershighers 를 PriorityQueue로 생성한다. 이 때, lowers는 highers와 다르게 작은 값이 맨뒤로 가야하기 때문에 새로운 Comparator를 사용하여 생성하였다.
  2. 반복문을 돌며 addNumber , rebalance, getMedian함수를 반복하며 sum 변수에 결과값을 더해준다.
  3. sum을 출력한다.

이런 식으로 구조가 나뉘어 있다.

먼저 addNumber함수를 보자.

이 함수는 단순히 새로 들어온 숫자가 lowers에 들어갈지 highers에 들어갈 지를 결정해준다. 각 Heap의 원소의 갯수는 전혀 상관하지 않는다. ( 다음에 나올 rebalance함수에서 처리해 줄 것이다. )

이제 rebalance함수를 보면

여기서는 두 Heap중 더 큰 Heap과 작은 Heap을 찾아내고, 각각의 Heap의 원소의 갯수가 2개이상 차이가 나면( 2개이상 원소갯수가 차이가 나면 중간값을 찾을수가 없으므로 )
더 큰 Heap에서 Head에 있는 값을 더 작은 Heap으로 이동시키다.

이제 각각의 Heap에 각각 작은 값들과 큰 값들이 담겨있으므로 중간값을 구하기 매우 수월해졌다.

마지막으로 getMedian함수를 보면

여기서는 두 Heap의 사이즈가 같은 경우에는 문제에서 둘중 더 작은 값을 제출하라고 하였기에 lowers에서 값을 가져와 return해주었고, 그렇지 않은 경우에는 원소가 하나 더 많은 Heap에서 peek() 해서 return을 해주었다.

이렇게 하여 문제를 풀었다.

참고로 위 코드는 유튜브 Data Structures: Solve 'Find the Running Median' Using Heaps 를 보면 더 이해가 쉬울 것이다. ~~ 코드는 사실 거의 같다... ~~


아직 모르는게 많아 게시글에 잘못된 정보가 있을 수 있습니다. 혹시 잘못된 정보가 있다면, 댓글 혹은 메일로 알려주시면 최대한 빨리 수정하겠습니다!

profile
공부하는 학생입니다

0개의 댓글