프로그래머스 힙

문제

풀이

import java.util.*;

class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        PriorityQueue<Integer> pq = new PriorityQueue();

        for (int n : scoville) {
            pq.offer(n);
        }

        while (!pq.isEmpty()) {
            int current = pq.poll();
            if (current < K) {
                if (pq.size() == 0) { // 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없음
                    return -1;
                }
                int next = pq.poll();
                int sum = current + next * 2;
                pq.offer(sum);
                answer++;  
            }
        }
        
        return answer;
    }
}

우선순위 큐를 이용하여 풀 수 있다.

결과

문제

풀이

import java.util.*;

class Solution {
    public int solution(int[][] jobs) {
        int answer = 0;
		int end = 0; // 수행되고난 직후의 시간
		int index = 0; // jobs 배열 인덱스
		int count = 0; // 수행된 작업 갯수

		// jobs 배열 오름차순 정렬 (요청시간 기준으로 오름차순)
		Arrays.sort(jobs, (o1, o2) -> o1[0] - o2[0]);
		// 처리 시간 기준으로 오름차순 정렬되는 우선순위 큐
		PriorityQueue<int[]> pq = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

		while(count < jobs.length) {
			// 하나의 작업이 완료되는 시점까지 들어온 요청들을 큐에 넣기
			while(index < jobs.length && jobs[index][0] <= end) {
				pq.add(jobs[index++]);
			}

			if (pq.isEmpty()) {
				end = jobs[index][0]; // 작업 완료 이후에 요청 다시 받기 위해

			} else { // 작업 끝나기 전 들어온 요청 중에 수행시간이 가장 짧은 요청부터 수행
				int[] temp = pq.poll();
				answer += temp[1] + end - temp[0];
				end += temp[1];
				count++;
			}
		}

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

결과

문제

풀이

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        PriorityQueue<Integer> pq = new PriorityQueue<>(); // 최소 힙
        PriorityQueue<Integer> mpq = new PriorityQueue<>(Collections.reverseOrder()); // 최대 힙

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

            //빈 큐에 데이터를 삭제 요청할 경우 연산 무시
            if (pq.size() < 1 && op.equals("D")) {
                continue;
            }

            //삽입 시 최소 힙, 최대 힙에 value 넣기
            if (op.equals("I")) {
                pq.offer(value);
                mpq.offer(value);
                continue;
            }

            // value값이 0보다 작은 경우 최소 힙에서 poll한 후 최대 힙에서 해당 원소 삭제
            if(value < 0) { 
                mpq.remove(pq.poll());
                continue;
            }
            pq.remove(mpq.poll());
        }
        
        if(pq.size() > 0 ) {
            answer[0] = mpq.poll();
            answer[1] = pq.poll();
        }
        
        return answer;
    }
}

결과