[알고리즘] 더 맵게

포인트

1. Heap 문제 임을 기억하고 알아보자

Heap은 무엇일까?

Heap은 완전 이진 트리 이며, `우선 순위가 높은` 노드가 루트 쪽에 가까운 자료구조를 말합니다. 또 이를 구현한 것이 priority_queue (우선순위 큐) 입니다. 우선 순위에 따라서 min_heap, max_heap 이라고 합니다. 

이 문제의 경우는 min_heap 을 사용하는 것이 현명하다고 생각합니다. 

 

🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 

기존 문제 그대로 푼 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>

using namespace std;

int solution(vector<int> vc, int K) {
	int answer = 0;

	while (vc.size() != 1) {
		// 원소 1개만 남으면 종료
		sort(vc.begin(), vc.end()); //먼저 정렬을 해줍니다. 
		int a = vc.front(); vc.erase(vc.begin());
		int b = vc.front(); vc.erase(vc.begin());//1 //2
		
		int c = a + 2 * b; //new 새로 넣어준다.
		vc.insert(vc.begin(), c); // 맨 앞에 넣어 죽;
		answer += 1; // 최솟값이 K이상인지 확인
		int min_value = *min_element(vc.begin(), vc.end());
		if (min_value >= K) break; // K 이상이면 횟수 리턴
	}

	if (vc.size() == 1 && vc.front() < K) return -1;
	
	return answer;
}

문제의 적힌 한글을 그대로 코드로 넣어놓은 모습입니다.  (정확성 O, 효율성 X)

그럼 이 상황에서 고려를 해야 할 것은 ? (자료구조를 바꾸는 것입니다. )

우선순위 큐로 변경

#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
	int answer = 0;
	int new_value;
	priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());
	// 이런 방식으로 넣어주면 반복문 없이 바로 자료구조에 값을 넣어줄 수 있습니다.
	// 또한 자동으로 우선순위를 따라갑니다. 
	
	while (pq.top() < K) {
		if (pq.size() == 1) return -1;
		new_value = pq.top();
		pq.pop();
		pq.push(new_value + pq.top() * 2); // 스코빌 값을 넣어줍니다.
		pq.pop();
		answer+=1;
	}

	return answer;
}

Java

import java.util.*;
import java.util.stream.Collectors;

class Solution {

    public static int solution(int[] scoville, int K) {
        int answer = 0;
        ArrayList<Integer> vc = Arrays.stream(scoville).boxed().collect(Collectors.toCollection(ArrayList::new));

        while (vc.size()!=1){
            Collections.sort(vc);
            int a = vc.get(0); vc.remove(0);
            int b = vc.get(0); vc.remove(0);

            int c = a+2*b;
            vc.add(0, c);
            answer+=1;
            int min_value = Collections.min(vc);
            if(min_value>=K) break;
        }

        if(vc.size()==1&&vc.get(0)<K) return -1;

        return answer;
    }

}

 

 

우선순위 큐로 변경 (최소 힙이 디폴트 값, 최대 힙을 만들고 싶은면 Collections.reverseOrder()

import java.util.*;
import java.util.stream.Collectors;

class Solution {

    public static int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int ele : scoville){
            pq.add(ele);
        } // min heap // 기본

        int new_value;
        while(pq.peek()<K){
            if(pq.size()==1) return -1;
            if(pq.size()>=2){
                new_value = pq.poll();
                pq.add(new_value+pq.peek()*2);
                pq.poll();
                answer+=1;
            }
        }
        
        return answer;
    }

}

2021 03 15 추가
python

파이썬으로 수정하는 버전 입니다.

import heapq


def solution(scoville: list, K: int) -> int:
    heapq.heapify(scoville)
    answer = 0

    while True:
        first = heapq.heappop(scoville)

        if first >= K:
            break

        if len(scoville) == 0:
            return -1

        second = heapq.heappop(scoville)
        heapq.heappush(scoville, fist+second*2)
        answer += 1
    return answer

파이썬 라이브러리는 공식적으로 max heap 을 지원하지 않기 때문에
- 값을 넣어주면서 다시
- 값을 곱해주면서 계산하면 👍