7월 31일 99클럽 항해 10일차

99클럽 항해 10일차

 

오늘의 문제는 이중우선순위큐 이다.

 

문제에서 우선순위 큐를 사용하여 최댓값과 최솟값을 구하는 문제가 되겠다.

        -> 우선순위 큐(최소힙과 최대힙)를 생성한다.

        -> 문자열 배열의 각 단어를 비교하여 I가 들어간 경우 우선순위 큐(pq)와 역 우선순위 큐(repq) 모두 값을 넣어준다.
        -> 문자열 배열의 각 단어를 비교하여 D 1 이 들어간 경우 repq에서 우선순위가 가장 높은 값(최댓값)을 지워주고 해당 값을 pq에서도 지워준다.

         -> 문자열 배열의 각 단어를 비교하여 D -1 이 들어간 경우 pq에서 우선순위가 가장 높은 값(최솟값)을 지워주고 해당 값을 repq에서도 지워준다.

        -> 모든 실행을 끝낸 후 큐가 비어있으면 [0,0], 큐에 내용이 있으면 [최댓값,최솟갓]을 출력한다.

순서로 문제를 해결하였다.

 

import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    public int[] solution(String[] operations) {

        int[] answer = new int[2];

        //우선순위 큐에
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        PriorityQueue<Integer> repq = new PriorityQueue<Integer>(Collections.reverseOrder());


        for(int i = 0; i < operations.length; i++){
            if(operations[i].contains("I")){
                //숫자 큐에 주어진 숫자 삽입
                repq.add(Integer.parseInt(operations[i].substring(1).trim()));
                pq.add(Integer.parseInt(operations[i].substring(1).trim()));
            }
            else if(operations[i].contains("D 1")){
                //최댓값 삭제
                pq.remove(repq.poll());
            }
            else if(operations[i].contains("D -1")){
                //최솟값 삭제
                repq.remove(pq.poll());
            }
        }
        if(pq.isEmpty()||repq.isEmpty()){
            answer[0] = 0;
            answer[1] = 0;
        }
        else{
            answer[0] = repq.peek();
            answer[1] = pq.peek();
        }
        return answer;
    }
}