[프로그래머스 / Java] 이중우선순위큐 (Lv.3)

문제 풀이 날짜: 2023.05.03
포스트 작성일: 2023.05.21

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

프로그래머스 코딩테스트 고득점Kit 힙 편 : 이중우선순위큐 (Lv.3) (문제 링크)

 

키워드

우선순위 큐, Comparator

 

풀이 접근법

• 최대로 정렬하는 PriorityQueue와, 최소로 정렬하는 PriorityQueue를 정의한다.
• Comparator를 이용해서 정렬 기준을 아래와 같이 새로 정해주어야 한다.

//방법 1
PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
//Collections에도 reverseOrder()가 존재한다.

//방법 2
PriorityQueue<Integer> pq = new PriorityQueue<>(
				(o1, o2) -> Integer.compare(o2, o1)); //o1, o2의 순서가 반대임에 주의

 

코드

import java.util.*;

public class DualPriorityQueue {
	public int[] solution(String[] operations) {
        int[] answer = new int[2];
        
        PriorityQueue<Integer> minPq = new PriorityQueue<>();
        PriorityQueue<Integer> maxPq = new PriorityQueue<>(
            Comparator.reverseOrder());
        
        for(String operation : operations) {
            String[] temp = operation.split(" ");
            
            String operator = temp[0];
            int operand = Integer.parseInt(temp[1]);
            
            if(operator.equals("I")) {
                minPq.add(operand);
                maxPq.add(operand);
            }
            else if(operator.equals("D")) {
                if(minPq.isEmpty()) {
                    continue;
                }
                
                if(operand > 0) { //최댓값 삭제
                    int key = maxPq.poll();
                    minPq.remove(key);
                }
                else { //최솟값 삭제
                    int key = minPq.poll();
                    maxPq.remove(key);
                }
            }
        }
        
        if(minPq.isEmpty()) {
            return answer;
        }
        
        answer[0] = maxPq.poll();
        answer[1] = minPq.poll();
        
        return answer;
    }
}

---

정렬 기준이 다른 두 힙을 구현하기만 하면 쉽게 풀 수 있는 문제이다. Comparator를 이용한 Collection의 정렬은 알아두면 여러곳에 응용할 일이 많으니 확실히 익혀두는 것이 좋겠다.

 

git 링크

https://github.com/jinju9553/23-CodingTest/blob/main/week7/day1/DualPriorityQueue.java