[알고리즘] 그리디(greedy) + 힙(heap) 을 같이 써보자

코딩테스트 연습 - 라면공장

이 문제는 이틀에 걸쳐서 4가지 방법으로 푼 문제이다. (사실 힙으로 한번에 풀고 재미삼아 다른방법으로도 풀어봤다)

1. 전체탐색

 1-1. DFS - 재미삼아 이렇게 풀어봤다가 4시간동안 삽질끝에 결국 풀었지만, 효율성에서 영혼까지 털렸다.

2. 그리디

 2-1. getMax 를 이용한 풀이

 2-2. Collections.sort 를 이용한 풀이

 2-3. 우선순위 큐를 이용한 풀이

역시 가장 효율성이 높은 방법은 4번째 방법이다. 그 이유는 현재 stock 으로 버틸때 까지 버티다가 이전에 공급받은 밀가루를 공급받을 때, 그리디하게 최대 공급량을 받게된다. 즉 매번 밀가루 공급량의 최댓값을 찾을 때의 시간복잡도가 O(logn) 으로 가장 빠르다. 

각각의 시간복잡도는 다음과 같다.

 n^2  n  nlogn  logn

1번을 제외한 나머지 3가지 풀이에서 모두 효율성 테스트까지 통과하였다. 

1번 풀이의 경우 시간초과가 나는데, 그 이유를 아직 잘 모르겠다(추측컨대 무한루프에 빠지는 것 같다..?)

 

1) DFS 를 이용한 풀이

참담하군... 

 

2) getMax 를 이용한 풀이

O(n) 이므로 두번째로 빠른 방법이다

 

3) Collections.sort 를 이용한 풀이

O(nlogn) 으로 세번째로 빠르다

 

4) 우선순위 큐를 이용한 풀이

O(logn)으로 역시 가장빠른 효율성을 보여준다

꼭 힙을 이용해서 풀 필요는 없지만, 데이터의 길이가 현재 문제에서 보다 더 길게 주어진다면 반드시 힙을 사용해야 하는 문제이다. 위 효율성 테스트 결과를 봐도 힙이 가장 빠름을 알 수 있다.