[프로그래머스][Java][Lv.3] 이중우선순위큐

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

프로그래머스

 

첫번째 풀이

1. 최소힙, 최대힙 우선순위큐를 만든다.
2. 입력된 문자열 배열을 순회하면서 명령어와 수신 탑을 확인한다.
3. 최소힙을 기준으로 하되, 최댓값에 대한 연산(D -1)이 필요할 경우, 임시적으로 생성된 최대힙에 최소힙을 넣고 최댓값을 제거한 뒤, 다시 최소힙에 넣는다
4. 어차피 Collections 객체는 힙영역에 저장되기 때문에 GC가 unreachable한 메모리는 삭제할거라 메모리 걱정안해도 될 것 같다.

import java.util.*;
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 (int i = 0; i < operations.length; i++) {
            String[] split = operations[i].split(" ");
            String first = split[0];
            String second = split[1];
            if (first.equals("I")) {
                minheap.offer(Integer.parseInt(second));
            }
            else {
                if (!minheap.isEmpty()) {
                    if (second.equals("-1")) { // 최솟값
                        minheap.poll();
                    } else if (second.equals("1")) { // 최댓값
                        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
                        max.addAll(minheap);
                        max.poll();
                        minheap.clear();
                        minheap.addAll(max);
                    }
                }
            }
        }
        maxheap.addAll(minheap);
        answer[0] = !maxheap.isEmpty() ? maxheap.poll() : 0;
        answer[1] = !minheap.isEmpty() ? minheap.poll() : 0;
        return answer;
    }
}

테스트 1 〉	통과 (0.75ms, 79.9MB)
테스트 2 〉	통과 (0.52ms, 75MB)
테스트 3 〉	통과 (0.51ms, 71.4MB)
테스트 4 〉	통과 (0.48ms, 77.8MB)
테스트 5 〉	통과 (0.70ms, 76.9MB)
테스트 6 〉	통과 (0.52ms, 78.6MB)

 

 

두번째 풀이

위의 풀이처럼 임시로 다시 map객체를 생성해주는 대신 remove함수로 지정된 객체를 큐에서 삭제한다.

아래 코드가 더 간단해보이긴한데, remove함수는 해당 객체의 위치를 찾아 삭제하는 데 O(n)의 시간이 소요된다.

반면에 poll함수는 가장 우선순위가 높은(최솟값 또는 최댓값) 요소를 제거하고 반환하기 때문에 O(log n) 시간이 걸린다.

시간 복잡도에서는 remove(Object o)가 poll()에 비해 더 높다. 하지만 서로 성능적인 측면에서는 별로 차이가 없을 것 같다.

import java.util.*;
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 (int i = 0; i < operations.length; i++) {
            String[] split = operations[i].split(" ");
            String first = split[0];
            String second = split[1];
            if (first.equals("I")) {
                int num = Integer.parseInt(second);
                minheap.offer(num);
                maxheap.offer(num);
            } else {
                if (!minheap.isEmpty()) {
                    if (second.equals("-1")) { // 최솟값 삭제
                        int minTop = minheap.poll();
                        maxheap.remove(minTop);
                    } else if (second.equals("1")) { // 최댓값 삭제
                        int maxTop = maxheap.poll();
                        minheap.remove(maxTop);
                    }
                }
            }
        }

        answer[0] = (!maxheap.isEmpty()) ? maxheap.poll() : 0;
        answer[1] = (!minheap.isEmpty()) ? minheap.poll() : 0;
        return answer;
    }
}

테스트 1 〉	통과 (0.62ms, 82.7MB)
테스트 2 〉	통과 (1.03ms, 73.3MB)
테스트 3 〉	통과 (0.87ms, 72.6MB)
테스트 4 〉	통과 (1.00ms, 76.2MB)
테스트 5 〉	통과 (0.74ms, 68.2MB)
테스트 6 〉	통과 (0.48ms, 73.1MB)