프로그래머스 3단계 : 이중우선순위큐 (Java 자바)

문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

 

 

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

 

입출력 예

 

풀이

처음엔 ArrayList를 사용하려고 했으니 최댓값, 최솟값을 구할 때 ArrayList를 사용하면 시간초과 및 효율성이 떨어진다는 걸 알게되었습니다.

이런 문제는 우선순위큐로 접근하는 게 더 좋습니다! (PriorityQueue를 사용하는 문제)

1. 최대값을 삭제할 때는 최대힙에서 poll() 을 사용하고, 최소힙에서 remove() 함수로 삭제
2. 최소값을 삭제할 때는 최소힙에서 poll() 을 사용하고, 최대힙에서 remove() 함수로 삭제

* PriorityQueue에 대한 내용은 추후 정리 후 업로드

 

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

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

        int[] answer = new int[2];

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 연산
        for (String op : operations) {

            // 삽입
            if (op.substring(0,1).equals("I")) {
                int value = Integer.valueOf(op.substring(2));     
                minHeap.offer(value);
                maxHeap.offer(value);          
            } 
                     
            // 값이 있을 때
            else if (!minHeap.isEmpty()) {
                
                // 최대값 remove
                if (op.equals("D 1")) {
                    int value = maxHeap.poll();
                    minHeap.remove(value);
                }

                // 최소값 remove
                else if (op.equals("D -1")) {
                    int value = minHeap.poll();
                    maxHeap.remove(value);       
                }
            }            
        }

        // 값이 있을 때
        if (!minHeap.isEmpty()) {
            answer[0] = maxHeap.peek();
            answer[1] = minHeap.peek();
        }

        return answer;
    }
}