본문 바로가기

알고리즘 공부 및 문제 풀이/프로그래머스(PRO)

[pro] 프로그래머스 level3 42628 이중우선순위큐 (Java) - heap

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/42628

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

[풀이]

최대힙, 최소힙 두개를 만들어서 사용하면 쉽게 해결 가능하다. 

두 개의 우선순위큐에서 모두 삭제되어야 하기 때문에 remove(Object o)를 이용한다.

 

[코드]

 

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        PriorityQueue<Integer> minpq = new PriorityQueue<>();
        PriorityQueue<Integer> maxpq = new PriorityQueue<>(Collections.reverseOrder());
        
        for(String s:operations){
            String type = s.substring(0, 1);
            if(type.equals("I")){
                int num = Integer.parseInt(s.substring(2));
                minpq.add(num);
                maxpq.add(num);
            }
            else if(type.equals("D") && !maxpq.isEmpty() && !minpq.isEmpty()){
                if(s.charAt(2)=='-'){
                    //최솟값 삭제
                    int min = minpq.poll();
                    maxpq.remove(min);
                }
                else{
                    //최댓값 삭제
                    int max = maxpq.poll();
                    minpq.remove(max);
                }
            }
        }
        
        if(!minpq.isEmpty() && !maxpq.isEmpty()){
            answer[0] = maxpq.poll();
            answer[1] = minpq.poll();
        }
        else{
            answer[0] = 0;
            answer[1] = 0;
        }
        
        return answer;
    }
}