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

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

프로그래머스

알고리즘 분류

• 힙(heap)

 

풀이

요소를 넣을때마다 정렬하는게 아니고 넣을 때 자기 자리를 찾아 넣는PriorityQueue 를 이용해서 풀었다.

하지만 Queue특성인 FIFO때문에 제일 큰 숫자가 뒤에 있으므로 poll을 함수를 사용해 삭제할 순 없었다.

그래서 temp 라는 큰 숫자가 앞에오는(내림차순인) PriorityQueue를 하나 더 선언했다.

​

로직은 간단하다.

숫자가 들어오면 두개의 Queue에 다 넣어주고

"D" 문자열이 들어오면 삭제해야 하니

1이면 temp에서 poll(), -1이면 queue에서 poll() 함수를 사용 했다.

그리고 두queue의 요소가 일치 해야 하므로 다른 큐에 remove()함수를 사용했다.

 

아래는 전체 정답 코드이다.

import java.util.*;

class Solution {
    PriorityQueue<Integer> queue = new PriorityQueue<>();
    PriorityQueue<Integer> temp = new PriorityQueue<>( (o1,o2) -> o2-o1 );
    
    public int[] solution(String[] operations) {
        // init
        int[] answer ;
        String code;
        int number;
        
        String line [] ;
        for(int i = 0 ; i < operations.length ; i++){
            line = operations[i].split(" ");
            code = line[0];
            number = Integer.parseInt(line[1]);
            
            if(code.equals("I")){
                queue.add(number);
                temp.add(number);
            }else{
                if(queue.isEmpty()) continue;
                
                if(number == -1){
                    int z = queue.poll();
                    temp.remove(z);
                }else if(number == 1){
                    int a = temp.poll();
                    queue.remove(a);
                } // else if
                
            } //else
            
        } // for
        
        if(queue.isEmpty()){
            answer = new int[]{0, 0};
        }else{
            answer = new int[]{temp.peek(), queue.peek()};
        }
        return answer;
    }
}