[알고리즘] 프로그래머스 스쿨 - 힙(Heap) 문제 풀이 ( 더 맵게, 디스크 컨트롤러, 이중우선순위 큐 )

힙과 관련된 문제 모음입니다. 힙은 특정한 규칙을 가지는 트리로, 우선 순위 큐를 구현하는 자료구조입니다. ( 최대 힙, 최소 힙) 그래서 대게 해당 문제들은 우선 순위큐를 사용하면 손쉽게 문제 풀이를 할 수 있습니다. 우선 순위 큐를 사용한는 케이스를 제 경험으로 정리하면 아래와 같습니다.

1. 입력의 크기가 너무 커서, 입력과 동시에 정렬이 필요한 문제 ( Level 2 - 더 맵게, Level 3 - 이중우선순위큐 )
2. 그리디 알고리즘 적용에서 정렬이 필요한 경우 혹은 최대값, 최소값 기준 정렬  ( Level3 - 디스크 컨트롤러 )

1번 경우에 백준 14729(칠무해)를 연관문제로 보면되고, 2번의 경우에는 컵라면, 순회강연 문제를 함께 참고하면 좋을듯합니다.

---

입력의 크기가 너무 커서 입력과 동시에 정렬을 하면 유리한 문제

 

프로그래머스 '더 맵게' 문제

풀이 방법

• 입력으로 주어지는 값이 큰 경우입니다.입력과 동시에 오름차순으로 정렬하면 편리합니다.
• 저는 입력 내용을 탐색 과정에서 K보다 작아서 스코빌 지수 계산 적용대상만 우선순위큐에 넣었습니다.
• 스코빌 지수 계산 적용대상들을 가지고 반복문을 돌면서 계산하여 지수를 계산합니다.
• 최종적으로 우선순위큐에 하나가 남으면 스코빌 지수를 적용할 수 없으므로 -1을 리턴합니다.
• 그렇지 않다면 결과를 리턴합니다.

코드

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        boolean flag = false;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int i = 0 ; i < scoville.length; i++){
            if(scoville[i] < K)
                pq.offer(scoville[i]);
        }
        
        
        while(pq.peek() <= K){
            if(pq.size() == 1) return -1;   
            
            int first = pq.poll();
            int second = pq.poll();
            pq.offer(first + (second * 2));
            answer++;
        }
        
        return answer;
    }
}

 

 

프로그래머스 '이중우선순위큐' 문제

풀이 방법

• 문제에서 이미 힌트를 주고 있습니다. 우선 순위큐를 두개를 사용하면 됩니다.
• 오름차순, 내림차순 각각 우선순위큐를 하나씩 만듭니다.
• 주어진 조건을 탐색하면서 큐에 입력이 발생하는 부분은 두개의 큐 모두 입력합니다.
• 최소값 빼는 경우, 오름차순 정렬 큐에서 poll()을 진행하고 내림차순 정렬 큐에서는 remove(poll())을 진행합니다.
• 반대로 최대값 빼는 경우, 내림차순 정렬 큐에서는 poll()을 진행하고 오름차순 정렬 큐에서는 remove(poll())을 진행합니다.

import java.util.*;

class Solution {
    
    private final static String D_MAX = "D 1";
    private final static String D_MIN = "D -1";
    
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        // 문제에서 주어준 힌트
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(String s : operations) {
            
            if(s.equals(D_MAX)){
                if(pq.isEmpty()) continue;
                int max = maxPq.poll();
                pq.remove(max);
            } else if(s.equals(D_MIN)){
                if(pq.isEmpty()) continue;
                int min = pq.poll();
                maxPq.remove(min);
            } else {
                pq.offer(Integer.parseInt(s.split(" ")[1]));
                maxPq.offer(Integer.parseInt(s.split(" ")[1]));
            }
            // System.out.println(pq);
        }
        
        if(pq.size() > 0) {
            answer[0] = maxPq.peek();
            answer[1] = pq.peek();
        }
        
        return answer;
    }
}

---

최대값, 최소값 기준으로 정렬이 필요한 경우

프로그래머스 '디스크 컨트롤러' 문제

풀이 방법

• 평균이 최소가 되는 값을 구합니다.
• 입력이 문제의 예시처럼 오름차순으로 들어오지 않을 수 있습니다. 이를 요청 시간 순서로 정렬이 필요합니다.
• 현재 종료 시간보다 요청 시간이 작은 요청들을 모두 우선순위 큐에 넣습니다.
• 큐에서 하나씩 처리해야 될 것을 꺼내면서 종료 시간을 체크하고 이어서 계속 처리를 합니다.
• 이런 류의 문제에서 소요시간을 어떻게 정의하는지 반드시 확인을 해야합니다. 현재 소요시간은 "대기 시간 + 처리 시간 - 요청시간"인데 대기 시간이 지난 요청이 걸린 시간이 되므로 해당 값을 다음 연산에 갱신을 해주어야 합니다.

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        int cnt = 0;
        int end = 0;
        int idx = 0;
        
        Arrays.sort(jobs, (o1,o2)->o1[0] - o2[0]);
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);
        
        while(cnt < jobs.length) {
            
            while(idx < jobs.length && jobs[idx][0] <= end){
                pq.offer(jobs[idx++]);
            }
            
            if(pq.isEmpty()) {
                end = jobs[idx][0];
            } else {
                int[] temp = pq.poll();
                answer += temp[1] + end - temp[0];
                end += temp[1];
                cnt++;
            }
        }
        
        return (int) Math.floor(answer / jobs.length);
    }
}

 

---

무튼 : 중요한 풀이 방법이다.