[프로그래머스-자바] 힙 Heap

더 맵게

• PriorityQueue 를 사용하는 문제
• heap은 정렬하지 않아도 peek()이나 poll()하면 가장 작은 값이 나온다.
• 힙은 우선순위 큐를 위해 만들어진 자료구조로, 부모노드 키 값이 자식 노드 키 값보다 항상 크거나 작다.

import java.util.PriorityQueue;

public class Spicer {
    public int solution(int[] scoville, int K) {
        int answer = 0;

        PriorityQueue<Integer> heap = new PriorityQueue();
        for (int i = 0; i < scoville.length; i++) {
            heap.add(scoville[i]);
        }

        while (heap.peek() > K) {
            if(heap.size() < 2) return -1;
            int a = heap.poll();
            int b = heap.poll();

            int c = a + 2 * b;
            heap.add(c);
            answer++;
        }
        return answer;
    }
}

 

디스크컨트롤러

• SJF (Short Job First) 짧은 작업 우선 처리 문제
• Job 클래스를 만들어서 변수 reqTime과 runTime을 만들어 좀 더 이해쉽게 구조화
• 우선순위큐 두 개를 만들어서 관리
  • 요청시간 짧은 순으로 정렬
  • 작업시간 짧은 순 정렬
• 요청시간 순으로 정렬한 큐에서 현재시간보다 작은 것들을 넣고, 그 중 empty가 되기 전까지 작업시간 순으로 더하고 벗어나게 되면 현재시간을 추가하는 식으로 합을 구한다.
• 어려워서 다시 풀어봐야할 문제!

import java.util.Comparator;
import java.util.PriorityQueue;

public class DiskController {
    class Job{
        int reqTime;
        int runTime;

        public Job(int req, int run){
            this.reqTime = req;
            this.runTime = run;
        }
    }

    public int solution(int[][] jobs) {
        int answer = 0;

        PriorityQueue<Job> q = new PriorityQueue(new Comparator<Job>() {
            @Override
            public int compare(Job o1, Job o2) {
                return o1.reqTime - o2.reqTime;
            }
        });

        for(int[] job:jobs){
            q.add(new Job(job[0],job[1]));
        }

        PriorityQueue<Job> pq = new PriorityQueue<>(new Comparator<Job>() {
            @Override
            public int compare(Job o1, Job o2) {
                return o1.runTime - o2.runTime;
            }
        });

        int count = 0;
        int sum = 0;
        int time = 0;

        while(count<jobs.length){
            while(!q.isEmpty() && time >= q.peek().reqTime){
                pq.offer(q.poll());
            }
            if(!pq.isEmpty()){
                Job j = pq.poll();
                sum += j.runTime + (time - j.reqTime);
                time += j.runTime;
                count++;
            }else{
                time++;
            }
        }
        answer = sum/count;
        return answer;
    }
}

 

이중우선순위큐

• 기본적으로 우선순위큐는 최소값이 우선순위형태여서 최대값 우선으로 정렬하려면 인자에 Collections.reverseOrder()를 넣으면 된다.
• 중간에 pq.isEmpty() 체크를 통해 빈 큐가 아닐 경우에만 삭제를 하도록 한다.

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class DoublePriorityQueue {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());

        for (String operation : operations) {
            StringTokenizer st = new StringTokenizer(operation);
            String word = st.nextToken();
            int value = Integer.parseInt(st.nextToken());

            if (word.equals("I")) {
                pq.add(value);
                maxPq.add(value);
            } else {
                if (!pq.isEmpty()) {
                    if (value < 0) {
                        int min = pq.poll();
                        maxPq.remove(min);
                    } else {
                        int max = maxPq.poll();
                        pq.remove(max);
                    }

                }
            }
        }

        if (!pq.isEmpty()) {
            answer[0] = maxPq.peek();
            answer[1] = pq.peek();
        }
        return answer;
    }
}