프로그래머스 자바 :: 힙(Heap)

이번주는 Heap 3문제

 

 

Heap

힙은 특정한 규칙을 가지는 트리로, 힙을 이용해서 우선순위 큐를 구현할 수 있습니다.

많은 언어에서 이미 구현된 우선순위 큐 라이브러리를 제공합니다. 이를 활용하면 효율적으로 문제를 풀 수 있습니다. 우선순위 큐를 이용해서 해결하기에 적합한 문제들을 만나보세요.

 

 

 

---

 

 

더 맵게

 

 

 

내 풀이

 

처음에 순서가 꼭 5,3,9,10,12 가 되어야 된다고 생각해서

우선순위 큐와 그냥 큐 두개를 구현하려고 했는데

그럴 필요가 없었다.

 

어차피 작은 것부터 계산하게 되니까

우선순위큐 하나로 해결 가능!

 

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        
        for (int food : scoville){
            queue.add(food);
        }

        while(queue.peek() < K){
            if(queue.size() < 2){
                return -1;
            }
            else {
                queue.add(queue.poll() + queue.poll() * 2);
                answer++;
            }
        }
                 
        return answer;
    }
}

 

 

 

 

---

 

 

이중우선순위큐

 

 

 

 

 

 

내 풀이

 

레벨 3이라 걱정했는데 뭐지...?

혼자서 생각보다 쉽게 풀었다!

 

음.. 다만 우선순위 큐를 사용하지 않았다 ㅠ_ㅠ

 

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2]; // 기본 설정이 [0,0]

        ArrayList<Integer> list = new ArrayList<>(); 

        for (int i = 0; i < operations.length; i++){
            if(operations[i].charAt(0) == 'I'){
                list.add(Integer.parseInt(operations[i].substring(2)));
            }
            
            if(operations[i].charAt(0) == 'D' && operations[i].charAt(2) == '-'){
                if(!list.isEmpty()){
                    list.remove(list.stream().min(Integer::compare).orElseThrow());
                }
            }
            
            if(operations[i].charAt(0) == 'D' && operations[i].charAt(2) == '1'){
                if(!list.isEmpty()){
                    list.remove(list.stream().max(Integer::compare).orElseThrow());
                }
            }
        }

        if (!list.isEmpty()){
            answer[0] = list.stream().max(Integer::compare).orElseThrow();
            answer[1] = list.stream().min(Integer::compare).orElseThrow();
        }
        
        return answer;
    }
}

 

 

 

 

다른사람 풀이

 

우선순위 큐를 사용하고 코드도 심플하다.

max와 min 각각의 큐를 구현하는 방식!

 

class Solution {
    public int[] solution(String[] operations) {
        Queue<Integer> minpq = new PriorityQueue<>();
        Queue<Integer> maxpq = new PriorityQueue<>(Collections.reverseOrder());

        for (String operation : operations) {
            if (operation.startsWith("I ")) {
                int n = Integer.parseInt(operation.substring(2));
                minpq.offer(n);
                maxpq.offer(n);
            } else if (!minpq.isEmpty() && operation.equals("D -1")) {
                maxpq.remove(minpq.poll());
            } else if (!maxpq.isEmpty() && operation.equals("D 1")) {
                minpq.remove(maxpq.poll());
            }
        }

        if (minpq.isEmpty() && maxpq.isEmpty()) {
            return new int[]{0, 0};
        }

        return new int[]{maxpq.poll(), minpq.poll()};
    }
}

 

 

 

 

---

디스크 컨트롤러

 

 

 

 

 

내 풀이

 

 

어렵다........

 

프로그래머스 42627 디스크 컨트롤러 JAVA