99클럽 코테 스터디 6일차 TIL: [프로그래머스] 이중우선순위큐

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

프로그래머스

풀이 1

처음에 푼 풀이는 다음과 같다.

• 최댓값과 최솟값을 구해야 하므로 큰 수를 우선으로 하는 우선순위 큐, 작은 수를 우선으로 하는 우선순위 큐 총 2개를 사용하면 된다.
• 그런데 하나의 큐에서 제거된 값이 여전히 다른 큐에는 남아있으므로, 두 큐에 공통되게 담긴 수를 의미하는 set을 두었다. 
• 그러고 하나의 큐에서 값을 제거할 때 정말 실제로 큐에 남아있는 값인지(두 큐에 공통되게 있는지) set.contains()를 통해 먼저 확인하는 과정을 거쳤다.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        Set<Integer> set = new HashSet<>();
        PriorityQueue<Integer> minQue = new PriorityQueue<>();
        PriorityQueue<Integer> maxQue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        
        for (String s : operations) {
            String op = s.split(" ")[0];
            int num = Integer.parseInt(s.split(" ")[1]);
            
            if (op.equals("I")) {
                set.add(num);
                minQue.add(num);
                maxQue.add(num);
            } 
            if (op.equals("D") && num == 1) {
                while (!maxQue.isEmpty()) {
                    int poll = maxQue.poll();
                    if (set.contains(poll)) {
                        set.remove(poll);
                        break;
                    }
                }
            } 
            if (op.equals("D") && num == -1) {
                while (!minQue.isEmpty()) {
                    int poll = minQue.poll();
                    if (set.contains(poll)) {
                        set.remove(poll);
                        break;
                    }
                }
            } 
        }
        
        int[] answer = new int[2];
        if (set.size() == 0) {
            return answer;
        }
        while (!maxQue.isEmpty()) {
            int poll = maxQue.poll();
            if (set.contains(poll)) {
                answer[0] = poll;
                break;
            }
        }
        while (!minQue.isEmpty()) {
            int poll = minQue.poll();
            if (set.contains(poll)) {
                answer[1] = poll;
                break;
            }
        }
        
        // 0, 0 또는 최댓값, 최솟값 반환
        return answer;
    }
}

풀이 2

앞선 풀이에서 set.contains()의 시간 복잡도가 O(1)이므로 공통된 수들을 담는 set을 사용했는데, 상황에 따라 비효율적일 수 있다는 생각이 들었다. 예를 들어 최소 힙에서 뺀 여러 개의 값이 최대 힙의 최댓값으로 존재하여, 최대 힙에서 값을 빼는데 최악의 경우 O(N)만큼의 시간이 걸릴 수 있기 때문이다. 따라서 다음과 같이 최소 힙과 최대 힙을 사용한 풀이도 참고하자. 참고로 다음 풀이에서 사용한 우선순위 큐의 remove() 메소드는 O(N)의 시간 복잡도를 갖는다.

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        Queue<Integer> maxQue = new PriorityQueue<>((o1, o2) -> o2 - o1);
        Queue<Integer> minQue = new PriorityQueue<>();
        
        for (String s : operations) {
            String op = s.split(" ")[0];
            int num = Integer.parseInt(s.split(" ")[1]);
        
            if (op.equals("I")) {
                maxQue.add(num);
                minQue.add(num);
            }
            if (op.equals("D") && num == 1) {
                if (maxQue.isEmpty()) continue;
                minQue.remove(maxQue.poll());
            }
            if (op.equals("D") && num == -1) {
                if (minQue.isEmpty()) continue;
                maxQue.remove(minQue.poll());
            }
        }
    
        int[] answer = new int[2];
        if (maxQue.size() == 0) {
            return answer;
        }
        answer[0] = maxQue.poll();
        answer[1] = minQue.poll();
        
        return answer;
    }
}

시간 복잡도 비교

풀이 1과 풀이 2의 시간 복잡도를 비교해보자.

• 풀이 1
  • operations의 길이 (M)
  • operation 처리 (N * logN)
    • 우선순위 큐에 add (logN) + set에 값을 넣기 (1)
    • while 문을 돌며 poll (최악의 경우 N) * ( 우선순위 큐에서 poll (logN) + set.contains()와 set.remove() (1) )
  • ➡️ O(M * N * logN) 
• 풀이 2 
  • operations의 길이 (M)
  • operation 처리 (N)
    • 우선순위 큐에 add (logN)
    • 우선순위 큐에서 poll (logN), 우선순위 큐에서 remove (N)
  • ➡️ O(M * N) 

•  

무작정 풀이 1을 떠올리고 set.contains()가 O(1)의 시간 복잡도이므로 효율적일 것이라고 생각했는데, 최악의 경우까지 고려해서 시간 복잡도를 생각했어야 했다. 다음에는 여러 방법을 떠올려 보고 시간 복잡도를 비교한 후에 최적의 풀이로 풀어보자.