[프로그래머스] 힙 - 더 맵게

문제를 읽고 배열로만 생각했을 때 풀이이다.

 

	static int solution(int[] scoville, int K) {
        int answer = 0;
        
        ArrayList<Integer> foods=new ArrayList<Integer>();
        
        //scoville 오름차순 정렬 후 ArrayList 초기화
        Arrays.sort(scoville);
        for(int i=0;i<scoville.length;i++) foods.add(scoville[i]);
        
        while(foods.get(0)<K) {
        	//모든 음식 스코빌 지수를 K이상으로 만들 수 없는 경우
        	if(foods.size()<2) {
        		answer = -1;
        		return answer;
        	}
        	answer++;
        	int first=foods.remove(0);
        	int second=foods.remove(0);
        	int newFood=first+second*2;
        	foods.add(newFood);
        	Collections.sort(foods); 	// 내림차순 재정렬
        }
        
        return answer;
    }

 

정확성은 다 맞았지만 , 효율성 문제를 해결해야 했다.

 

아무래도 이 문제가 힙 개념에 들어있는 문제다 보니 힙을 사용하여 문제를 해결하였다.

	static void min_heap(ArrayList<Integer> heap,int val) {
		heap.add(val);
		int p=heap.size()-1;
		
		while(p>1 && heap.get(p/2)>heap.get(p)) {
			int tmp=heap.get(p/2);
			heap.set(p/2, heap.get(p));
			heap.set(p,tmp);
			
			p/=2;
		}
	}
	
	static void delete(ArrayList<Integer> heap) {
		heap.set(1, heap.get(heap.size()-1));
		heap.remove(heap.size()-1);
		
		int pos=1;
		while((pos*2)<heap.size()) {
			int min=heap.get(pos*2);
			int minPos=pos*2;
			
			if((pos*2+1)<heap.size() && min > heap.get(pos*2+1)) {
				min=heap.get(pos*2+1);
				minPos=pos*2+1;
			}
			
			if(heap.get(pos)<min) break;
			
			int tmp=heap.get(pos);
			heap.set(pos, heap.get(minPos));
			heap.set(minPos, tmp);
			
			pos=minPos;
		}
	}
	
	static int solution(int[] scoville, int K) {
		int answer = 0;
        
		ArrayList<Integer> heap=new ArrayList<Integer>();
		heap.add(0);
		
		Arrays.sort(scoville);
		for(int i=0;i<scoville.length;i++) {
			min_heap(heap,scoville[i]);
		}
		
		while(heap.get(1)<K) {
			if(heap.size()<3) return -1;
			
			answer++;
			int first=heap.get(1);
			delete(heap);
			int second=heap.get(1);
			delete(heap);
			int addFood=first+second*2;
			min_heap(heap,addFood);
		}
        return answer;
    }
	

힙을 사용하다보니 힙 연산 관련된 함수들을 새롭게 작성해야 해서 코드가 길어지게 되었다...

힙 코드를 작성하는 훌륭한 연습문제가 되었다고 생각한다. 흑흑

 

다른 사람의 코드를 보니 대부분 우선순위 큐로 문제를 해결한 것 같다.

우선 순위 큐가 힙의 개념과 같아서.. 이미 라이브러리로 존재하는 우선순위 큐를 사용할 걸 그랬다..