2023.02.15(목) - 프로그래머스 고득점 Kit 스터디(힙)

- 더 맵게

    풀이 방법

        - 문제에서 "가장 맵지 않은 두 음식을 섞는다"고 제시

        - 우선 순위 queue 를 이용해 주어진 음식의 스코빌 지수를 정렬

        - 가장 위의 음식이 K 보다 크거나 같을때 까지 상위 두 음식을 조합 하여 다시 우선순위 queue 에 삽입

package suhyeongLee.Heap.More_spicy;

import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i = 0; i < scoville.length; i++){
            pq.add(scoville[i]);
        }

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

        return answer;
    }
}

---

 

- 디스크 컨트롤러

    풀이 방법

        - 요청 시간 부터 끝날때 까지의 시간들의 평균이 최소가 되기 위해선 수행 시간이 짧은 순서대로 수행해야 함

        - 하지만 수행 시간 별로 sort 후 차례로 시행하면 이전 작업이 끝나도 다음 작업 요청이 시행 되지 못하는경우가 있음

        - 따라서 요청 시간 별로 정렬 한 후 우선순위 queue 를 수행 시간기준으로 정렬 되도록 한다.

        - 코드의 설명 참조

우선 순위 큐를 이용하면 위와 같은 케이스에서 큐에 A, B, C, D 로 들어가지만 큐 내부에서 A, C, B, D 로 정렬 해 줌

package suhyeongLee.Heap.Disk_Controller;

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
        Arrays.sort(jobs, (c1, c2) -> c1[0]-c2[0]);
        PriorityQueue<int[]> pq = new PriorityQueue<>((c1, c2) -> c1[1]-c2[1]);

        int cnt = 0, time = 0, index = 0;

        while(cnt < jobs.length){
            // 요청 시간별로 정렬 후 작업이 끝나자 마자 다음 작업을 수행 할 수 있을때까지 수행
            while( (index < jobs.length) && (jobs[index][0] <= time) ){
                pq.add(jobs[index++]);
            }
            // 연속된 작업을 수행 후 queue 가 비어 있다면 하나도 수행 하지 못한 것 time 을 이동
            if(pq.isEmpty()) {
                time = jobs[index][0];
            // 수행 한 작업이 있다면 수행 한 시간 만큼 time 에 더해 주어 해당 시간 만큼 이동
            } else {
                int[] tmp = pq.poll();
                answer += tmp[1] + time - tmp[0];
                time += tmp[1];
                cnt += 1;
            }
        }

        answer = (int) Math.floor(answer / jobs.length);
        return answer;
    }
}

 

---

 

- 이중 우선순위 큐

    풀이 방법

        - 우선순위 큐에는 가장 마지막 값을 뺄 수 있는 기능이 없다.

        - 이를 해결 하기 위해 문제에 있듯 우선순위 큐를 2개 사용하여 문제 해결

 

        - 오름차순으로 정렬 하는 우선순위 큐와 내림차순으로 정렬하는 우선순위 큐를 모두 생성

        - 주어진 String 배열을 처음부터 끝까지 돌며 다음을 수행

            . string 이 "D 1" 일 경우 최대값을 삭제 해야 하기 때문에 최대 큐에서 poll 을 진행 하고 결과 값을 최소 큐에서 같이 제거 해 줌

            . string 이 "D -1" 일 경우 위 작업에서 최대 큐와 최소 큐를 바꾸어 작업

            . string 이 "I num" 일 경우 양쪽 큐에 num 을 int 로 변환 하여 삽입

package suhyeongLee.Heap.Double_priority_queue;

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

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        PriorityQueue<Integer> pq_min = new PriorityQueue<>();
        PriorityQueue<Integer> pq_max = new PriorityQueue<>(Collections.reverseOrder());

        for(int i = 0; i < operations.length; i++){
            if(operations[i].equals("D 1")){
                if(!pq_min.isEmpty()){
                    pq_min.remove(pq_max.poll());
                }
            } else if(operations[i].equals("D -1")){
                if(!pq_max.isEmpty()){
                    pq_max.remove(pq_min.poll());
                }
            } else {
                pq_min.add(Integer.parseInt(operations[i].split(" ")[1]));
                pq_max.add(Integer.parseInt(operations[i].split(" ")[1]));
            }
            System.out.println(pq_min);
            System.out.println(pq_max);
            System.out.println();
        }

        if(pq_min.isEmpty() && pq_max.isEmpty()){
            answer[0] = 0;
            answer[1] = 0;
        } else {
            answer[0] = pq_max.peek();
            answer[1] = pq_min.peek();
        }

        return answer;
    }
}