[200420] 힙 - 이중우선순위큐(level3)

1. 문제이해

- 상황에 맞게 최대값, 최소값을 삭제해야됨 --> 오름차순, 내림차순으로 그 때 그 때 정렬

- I 숫자 : substring을 통해 숫자만 뽑기

 

2. 전략

- pq : 숫자가 들어가있는 큐

- temp : 임시 큐(pq의 오름차순, 내림차순 모드를 바꾸는 동안 쓰는)

- directionUp : 오름차순, 내림차순 상태를 저장해둔 boolean

 

3. 참고했던 사항

- priorityqueue에서 Collections.reverseOrder()를 적용 시킨다.

(200419 - 디스크 컨트롤러 참고)

 

4. 코드

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        boolean directionUp = true; //오름차순
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        PriorityQueue<Integer> temp;
        int a = 0, b = 0;
        for(String s : operations){
            if((s.substring(0, 1)).equals("I")){ //삽입
                int num = Integer.parseInt(s.substring(2));
                pq.add(num);
            }
            else if(s.equals("D 1")){ //최대값
                if(directionUp){ //내림차순으로 맞춰주기
                    temp = pq;
                    pq = new PriorityQueue<>(Collections.reverseOrder());
                    pq.addAll(temp);
                    directionUp = false;
                }
                if(pq.size() != 0)  pq.remove();
            }
            else{ //최소값
                if(!directionUp){ //오름차순으로 맞춰주기
                    temp = pq;
                    pq = new PriorityQueue<>();
                    pq.addAll(temp);
                    directionUp = true;
                }
                if(pq.size() != 0)  pq.remove();
            }
        }
        
        int n = pq.size();
        while(pq.size() != 0){
            if(pq.size() == n)  a = pq.poll();
            if(pq.size() == 1)  b = pq.poll();
            else    pq.remove();
        }
        
        if(a > b){
            answer[0] = a;
            answer[1] = b;
        }
        else {
            answer[0] = b;
            answer[1] = a;
        }
        return answer;
    }
}

5. 다른 방법

- 현재 방법 : 큐는 두개 쓰면서 모드가 바뀔 때마다 계속 정렬 함수 씀 --> 시간이 오래 걸림

- 새로운 방법 : 오름차순 큐, 내림차순 큐를 따로 쓰기!!

   - I일 때는 둘다 add

   - D일 때 최대값이면 내림차순에서, 최소값이면 오름차순에서 poll한 후 그 값을 다른 큐에서도 remove

- 생각하지 못했던 원인 : pq.remove(값)이 가능한지 몰랐다!!알아두도록 하자!!