프로그래머스 고득점 Kit 하루만에 뽀개기 - 3. 힙 (Java, C++) 풀이

https://programmers.co.kr/learn/courses/30/parts/12117

프로그래머스

- 알고리즘 풀이로 C++를 주로 사용하다가 기업 코딩테스트를 위해 java 풀이를 학습하는 사람에게 도움이 될만한 포스트입니다. 알고리즘 적인 해설내용은 줄이고 C++에 익숙한 사람들이 Java 사용시 놓칠만한 내용 위주로 작성하고 있습니다.

- Queue<T> pq = new PrioiriyQueue<>(); // 최소힙(C++는 디폴트가 최대힙, 비교 연산자 초기값이 less<>). 헷갈릴 수 있음

1. 더 맵게

https://programmers.co.kr/learn/courses/30/lessons/42626 

코딩테스트 연습 - 더 맵게

- 모든 음식들을 공식에 따라 가장 맵지 않은 음식, 두 번째 맵지 않은 음식을 섞고 다시 큐에 넣어서 모든 음식의 값이 K 이상이 될 때까지 반복합니다. 최소힙에 모든 값들을 넣고 힙의 사이즈가 1이 되거나 가장 안 매운 음식(top)이 K 이상일 때까지 연산을 반복합니다

#include <vector>
#include <queue>
#include <functional>
using namespace std;

int solution(vector<int> scoville, int K) {
    int ans = 0;
    
    priority_queue<int, vector<int>, greater<int>> pq;
    for(int food : scoville) {
        pq.push(food);
    }
    
    while(pq.size() > 1 && pq.top() < K) {
        int fi = pq.top();
        pq.pop();
        int se = pq.top();
        pq.pop();
        
        int mix = fi + se * 2;
        ++ans;
        pq.push(mix);
    }
    
    if(pq.top() < K) return -1;
    return ans;
}

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int ans = 0;
        int N = scoville.length;
        
        Queue<Integer> pq = new PriorityQueue<>();
        for(int n: scoville) {
            pq.add(n);
        }
        
        while(pq.peek() < K && pq.size() > 1) {
            int fi = pq.poll(), se = pq.poll();
            int mix = fi + se * 2;
            ++ans;
            pq.add(mix);
        }
        
        if(pq.peek() < K) return -1;
        return ans;
    }
}

- Queue 메서드 정리

https://javadoc.scijava.org/Java13/java.base/java/util/Queue.html

 

2. 디스크 컨트롤러

https://programmers.co.kr/learn/courses/30/lessons/42627 

코딩테스트 연습 - 디스크 컨트롤러

- 운영체제에서 CPU 스케쥴링 기법 중 SJF 스케쥴링에 대해서 알아야된다. CPU를 한 작업이 점유하고 있고, 기다리고 있는 작업 중에서 수행 시간이 가장 짧은 것을 먼저 수행하면 average waiting time이 적게 걸린다. 

- 작업 요청시간이 빠른 순으로 작업을 처리 하되, 작업이 진행되는 동안 처리하지 못하는 다른 요청들을 최소힙에 담아 놓고 있다가, 그 다음으로 최소힙의 top값을 처리하는 식으로 작업들을 수행하고, 각 작업의 요청시간으로부터 실제 종료된 시간들을 모두 더해주고, 평균을 계산해준다. 

// C++
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

struct cmp {
    bool operator()(vector<int> a, vector<int> b) {
        return a[1] >= b[1];
    }
};

int solution(vector<vector<int>> jobs) { // 작업요청시간, 작업소요시간
    sort(jobs.begin(), jobs.end());
    
    int ans = 0, p = 0, nowt = 0, N = jobs.size();
    priority_queue<vector<int>, vector<vector<int>> pq;
    while(p < N || !pq.empty()) {
        if(p < N && jobs[p][0] <= nowt) {
            pq.push(jobs[p++]);
            continue;
        }
        if(!pq.empty()) {
            nowt += pq.top()[1];
            ans += nowt - pq.top()[0];
            pq.pop();
        } else {
            nowt = jobs[p][0];
        }
    }
    return ans / N;
}

// java
import java.util.*;

class Solution { // SJF
    public int solution(int[][] jobs) {
        Arrays.sort(jobs, (a, b) -> { // 작업 들어오는 순서
            if(a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
        });
    
        
        int ans = 0, p = 0, nowt = 0, N = jobs.length;
        Queue<int[]> pq = new PriorityQueue<>((a,b) -> {
            return a[1] - b[1]; // 짧은 Job 부터
        });
        
        while(p < N || !pq.isEmpty()) {
            if(p < N && jobs[p][0] <= nowt) {
                pq.add(jobs[p++]);
                continue;
            }
            
            if(!pq.isEmpty()) {
                nowt += pq.peek()[1];
                ans += nowt - pq.poll()[0];
            } else nowt = jobs[p][0];
        }
        
        return ans / N;
    }
}

- Comparator를 선언하거나, 위 풀이 처럼 람다식을 이용해줄 수 있다. 

 

3. 이중우선순위큐

- 최소힙, 최대힙을 하나씩 선언해서 문제에서 주어진 명령어를 그대로 구현하면 된다.

// C++
#include <string>
#include <vector>
#include <queue>
using namespace std;

vector<int> solution(vector<string> operations) {
    priority_queue<int, vector<int>> maxh;
    priority_queue<int, vector<int>, greater<int>> minh;
    int cnt = 0;
    
    for(string& s: operations) {
        if(!cnt) {
            while(!maxh.empty()) maxh.pop();
            while(!minh.empty()) minh.pop();
        }
        
        int num = stoi(s.substr(2));
        if(s[0] == 'I') {
            maxh.push(num);
            minh.push(num);
            cnt++;
        } else {
            if(!cnt) continue;
            if(num == 1) maxh.pop();
            else minh.pop();
            cnt--;
        }
    }
    
    if(cnt) return {maxh.top(), minh.top()};
    return {0, 0};
}

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] ans = new int[] {0,0};
        Queue<Integer> minh = new PriorityQueue<>();
        Queue<Integer> maxh = new PriorityQueue<>(Comparator.reverseOrder());
        
        for(String s: operations) {
            char cmd = s.charAt(0);
            int num = Integer.parseInt(s.substring(2));
            
            if(cmd == 'I') {
                minh.add(num);
                maxh.add(num);
            } else { // D 
                if(minh.isEmpty()) continue;
                
                if(num == 1) minh.remove(maxh.poll());
                else maxh.remove(minh.poll());
            }
        }
        
        if(!maxh.isEmpty()) {
            ans[0] = maxh.peek();
            ans[1] = minh.peek();
        }
        return ans;
    }
}

https://docs.oracle.com/en/java/javase/13/docs/api/java.base/java/util/Comparator.html

- Comparator 인터페이스에 정의된 Comparator.reverseOrder()를 사용해서 힙을 기존의 오름차순(최소힙)에서 내림차순(최대힙)으로 만들 수 있다.