(코테) 프로그래머스_이중우선순위큐 *힙

 

문제 링크

 

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

 

 

 

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
        //우선 순위 큐        
        
        // 공백을 기준으로 짜르기
        // I 는 삽입
        // D 는 삭제
        
        PriorityQueue<Integer> pqMin = new PriorityQueue<>(); //최소값
        PriorityQueue<Integer> pqMax = new PriorityQueue<>(Collections.reverseOrder());  //최대값
        
        for(String next : operations){
            //공백을 기준으로 배열로 나눔.
            String[] str = next.split(" ");            
            String type = str[0];
            int val = Integer.parseInt(str[1]);            
            
            if("D".equals(type) && !pqMin.isEmpty()){     //삭제 
                if(val==1){ //최대값                    
                    pqMin.remove(pqMax.poll());                    
                }else{               //최소값                            
                    pqMax.remove(pqMin.poll());
                }                
            }else if("I".equals(type)){                   //삽입
                pqMin.add(val);    
                pqMax.add(val); 
            }                        
        }
        
        if(pqMin.isEmpty())    return new int[]{0,0};        
    
        // 결과는 꺼내지 말고 읽기만
        int min = pqMin.peek();
        int max = pqMax.peek();
        return new int[]{max, min};
    }
}

회고

1. 이 방법과  TreeSet이 있다는걸 알았다. 

하지만 TreeSet도 생각은 했으나 get set이 복잡하게 일어나 시간복잡도가 비효율적일거 같아서 제외했는데 

막상 코드를 구현하다보니 우선순위큐도 복잡하긴 마찬가지라 오히려 가독성+ 효율성은 TreeSet이 더 좋을거 같다.

그리고 조회가 큐가 더 빠르기 때문에...

근데 큐에서 최솟값 삭제 *2개가 일어나기에..... 그닥 효율이 더 좋다고 말하긴 애매한

 

2. Priorityqueue 의 문법이 헷갈렸다 . 

    2-1. Collection.reverseOrder()  -> 내림차순 변경 

    2-2. remove로 큐 안에 특정값 삭제 가능, 마지막 값 꺼내기는 불가능.