231114 - 힙(Heap) : 우선순위 힙 기준 설정, 이중우선순위 큐

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/42626?language=java#

더 맵게

• 풀이
  1. 매운 지수가 가장 작은 두 값을 찾기 위해 우선순위 큐 생성
  2. Q의 최소 값이 K보다 작을 때까지 수행
     • 주의사항 : Q가 비어있을 때 poll을 할 경우 런타임 오류 발생, Q.size() 가 2 이상인지 확인
  3. a + 2 * b 값을 Q에 입력
  4. Q의 최소 값이 K를 넘지못할경우 -1, 나머지는 answer 리턴

import java.util.*;

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

        // 2
        while (Q.size() >= 2 && Q.peek() < K) {
            int a = Q.poll();
            int b = Q.poll();
            // 3
            Q.add(a + 2 * b);
            answer++;
        }

        //4
        if (Q.peek() < K) {
            return -1;
        } 
        return answer;
    }
}

[robert-min]

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

  디스크 컨트롤러(우선순위 힙 기준 설정)

• 풀이 :주석 참조

  
  import java.util.*;

class Solution {

public int solution(int[][] jobs) {
    int answer = 0;
    // 1 : 요청시간 기준을 정렬
    Arrays.sort(jobs, ((o1, o2) -> {
        return o1[0] - o2[0];
    }));

// System.out.println(Arrays.toString(jobs));

    // 2 : 진행시간 기준으로 출력하는 우선순위 큐
    int time = 0;
    int sum = 0;
    PriorityQueue<int[]> PQ = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

    int cnt = 0;
    int jobsIdx = 0;

    while (cnt < jobs.length) {

        while (jobsIdx < jobs.length && jobs[jobsIdx][0] <= time) {
            PQ.add(jobs[jobsIdx++]);
        }

        // 3 : PQ가 들어와있지 않는 경우 : time 조절
        if (PQ.isEmpty()) {
            time = jobs[jobsIdx][0];
        } else {
            int[] tmp = PQ.poll();
            sum += time + tmp[1] - tmp[0];
            time += tmp[1];
            cnt++;
        }

    }
    // 4 : 평균 계산 소수점 버림
    answer = (int)Math.floor(sum / jobs.length);

    return answer;

}

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/42628?language=java

이중우선순위 큐

• 풀이
  1. 최소힙 최대 힙 생성
  2. "I"로 시작할 경우 입력. 숫자를 파싱하기 위해 String.substring 사용
  3. "D 1"으로 시작할 경우 최대값을 제거. maxQ에서는 poll, minQ에서는 remove
  4. 아직 큐에 값이 남아 있을 경우 answer에 최대 최소값 입력

     
     import java.util.*;

class Solution {
public int[] solution(String[] operations) { // 1 PriorityQueue minQ = new PriorityQueue<>(); PriorityQueue maxQ = new PriorityQueue<>((o1, o2) -> (o2 - o1));

    for (String op : operations) {
        // 2
        if (op.startsWith("I")) {
            int n = Integer.parseInt(op.substring(2));
            minQ.add(n);
            maxQ.add(n);
        } else {
            // 3
            if (op.equals("D 1") && !maxQ.isEmpty()) {
                int delete = maxQ.poll();
                minQ.remove(delete);
            } else if (op.equals("D -1") && !minQ.isEmpty()) {
                int delete = minQ.poll();
                maxQ.remove(delete);
            }
        }
    }
    // 4
    int[] answer = new int[2];
    if (!maxQ.isEmpty() && !minQ.isEmpty()) {
        answer[0] = maxQ.poll();
        answer[1] = minQ.poll();
    }

    return answer;

}

}

[robert-min]

https://school.programmers.co.kr/learn/courses/30/lessons/42884#

단속카메라

• 풀이 : 주석 확인 참고

import java.util.*;

class Solution {
    public int solution(int[][] routes) {

        // 1 : 차량이 나가는 지점으로 정렬
        Arrays.sort(routes, ((o1, o2) -> o1[1] - o2[1]));
        // System.out.println(Arrays.toString(routes[routes.length-1]));

        // 2
        int cam = Integer.MIN_VALUE;
        int answer = 0;
        for (int[] route : routes) {
            // 캠이 설치된 위치보다 다음 루트가 크면 새로운 캠을 설치
            if (cam < route[0]) {
                cam = route[1];
                answer++;
            }
        }

        return answer;
    }
}