[프로그래머스/Java] 42628 이중우선순위큐

🔗 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

 

🔍  해결 과정

주어진 코드의 operations의 길이가 최대 100만이라 단순 배열을 활용해서 최댓값과 최솟값을 일일이 도출하기에는 시간적 문제가 존재하고, 문제에서의 이중우선순위 큐 연산 이야기를 하고 있으므로 이를 바탕으로 자바의 우선순위 큐 자료구조를 활용해야 함을 알 수 있습니다.

 

자세한 설명은 코드 주석에 첨부하였습니다.

---

✏️ 코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        Queue<Integer> pq = new PriorityQueue<>();
        
        for (String oper : operations) {
            String[] info = oper.split(" ");
            operand(pq, info[0], Integer.parseInt(info[1]));
        }
        
        // 최댓값 최솟값 출력하기
        if (pq.isEmpty()) {
            return new int[]{0, 0};
        }
        
        int[] result = new int[2];
        
        result[1] = pq.poll();
        
        if (pq.isEmpty()) {
            result[0] = result[1];
        } else {
            while (pq.size() > 1) {
                pq.poll();
            }
            result[0] = pq.poll();
        }
        return result;
    }
    
    // 우선순위큐는 최솟값을 우선으로
    private void operand(Queue<Integer> pq, String oper, int number) {
        if (oper.equals("I")) {
            pq.offer(number);
        } else if (oper.equals("D")) {
            if (pq.isEmpty()) {
                return;
            }
            
            if (number == 1) { // 최댓값 삭제 (맨 뒤에 존재함.)
                // 맨 뒤의 값을 가져오기 위해서 일단 큐에서 값을 다 빼버림
                Queue<Integer> pq_temp = new PriorityQueue<>();
                
                // 새로운 큐를 만들어서 이전 큐에 있는 마지막 값을 제외하고는 나머지 다 넣어주기
                while (pq.size() > 1) {
                    pq_temp.offer(pq.poll());
                }
                
                // 이전 큐에 업데이트 된 큐로 넣어두기 (복사해주기)
                pq.poll(); //최댓값 제거
                while (!pq_temp.isEmpty()) {
                    pq.offer(pq_temp.poll());
                }
                
            } else {
                pq.poll();
            }
        }
    }
}