99클럽 코테 스터디 10일차 TIL , 이중우선순위큐

문제

풀이

명령어가 String 배열로 들어온다.

명령어로는 "I"(INSERT), "D"(DELETE)가 있다.

INSERT는 말 그대로 정수를 입력하면 되고, DELETE로는 1이 들어오면 최댓값을 지우고 -1이 들어오면 최솟값을 지운다.

 

제출 1 - 오답

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
       
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        List<Integer> list = new ArrayList<>();
        list.add(Integer.MIN_VALUE);
        
        for(String str : operations){
            StringTokenizer st = new StringTokenizer(str);
            String method = st.nextToken();
            int val = Integer.parseInt(st.nextToken());
            
            if(method.equals("I")){
                if(val > list.get(list.size()-1)){
                    list.add(val);
                }
                heap.add(val);
            }else{
                if(val == 1){
                    if(heap.size() < 1) continue;
                    heap.remove(list.get(list.size()-1));
                    list.remove(list.size()-1);
                }else{
                    heap.poll();
                }
            }
        }
        int[] answer;
        if(heap.size() < 1){
            answer = new int[]{0,0};
        }else{
            answer =  new int[]{list.get(list.size()-1),heap.poll()};
        }
        
        return answer;
    }
}

 

heap을 하나만 쓰고 list에 max값들을 담아가면서 컨트롤 하려고 했다.

두 개의 테스트케이스를 통과하지 못했는데 이유는 찾지 못했다.

제출 2 - 정답

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
       
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for(String str : operations){
            StringTokenizer st = new StringTokenizer(str);
            String method = st.nextToken();
            int val = Integer.parseInt(st.nextToken());
            
            if(method.equals("I")){
                maxHeap.add(val);
                minHeap.add(val);
            }else{
                if(maxHeap.isEmpty() && minHeap.isEmpty()) continue;
                if(val == 1){
                    int max = maxHeap.poll();
                    minHeap.remove(max);
                }else{
                    int min = minHeap.poll();
                    maxHeap.remove(min);
                }
            }
        }
        int[] answer;
        if(maxHeap.size() == 0 && minHeap.size() == 0){
            answer = new int[]{0,0};
        }else{
            answer = new int[]{maxHeap.poll(), minHeap.poll()};
        }

        return answer;
    }
}

 

최대 힙 과 최소 힙을 구현해서 INSERT 일 경우는 모두 넣고,

DELETE일 경우에는 최대 값을 지울 경우 최대 힙에서 poll 후 같은 값을 최소 힙에서 지워준다.

어제의 문제를 우선순위큐로 해결했다면 어렵지 않게 풀이할 수 있는 것 같다.

 

TIL

• 어제 정리했던 Heap 자료구조를 다시 한번 풀이하면서 체득했다.