이중우선순위큐

Posted on Edited on In , ,

문제정의

일반적인 우선순위 큐에서 tail에서도 값이 나올 수 있게 만드는 문제이다. I + (숫자)인 경우 숫자를 삽입하는 것이고 "D 1"인 경우 최댓값을 제거하고, "D -1"이라면 최솟값을 제거한다. 이런 명령어들이 담긴 배열을 전부 수행하였을 때, 큐에 남은 최댓값과 최솟값을 배열로 담아 반환하면 된다. 문제링크

문제풀이

전체 코드는 다음과 같다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.util.*;

public class DoublePriorityQueue {

    //프로그래머스 문제풀이 level3 이중 우선순위 큐
    public static PriorityQueue<Integer> big;
    public static PriorityQueue<Integer> small;
    public static HashMap<Integer, Integer> big_map;
    public static HashMap<Integer, Integer> small_map;
    
    public static void main(String[] args) {
        String[] operations = {"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"};

        big = new PriorityQueue<Integer>(Collections.reverseOrder());
        small = new PriorityQueue<Integer>();

        big_map = new HashMap<>();
        small_map = new HashMap<>();


        for(String s : operations)
        {
            if(s.equals("D 1") && !big.isEmpty())
            {
                int big_i = big.peek();
                big_map.put(big_i, big_map.getOrDefault(big_i, 0)+1);
                big.poll();
                
            }
            else if(s.equals("D -1") && !small.isEmpty())
            {
                int small_i = small.peek();
                small_map.put(small_i, small_map.getOrDefault(small_i, 0)+1);
                small.poll();
            }
            else if(s.contains("I"))
            {
                int i = Integer.parseInt(s.substring(1).trim());
                big.add(i);
                small.add(i);
            }
            synchroize();
        }
        if(big.isEmpty())
            System.out.println(0);
        else
            System.out.println(big.peek());

        if(small.isEmpty())
            System.out.println(0);
        else
            System.out.println(small.peek());

    }
    public static void synchroize()
    {
        
        while(big_map.getOrDefault(big.peek(), 0) < small_map.getOrDefault(big.peek(), 0)
        && !big.isEmpty())
        {
            int big_i = big.peek();
            big_map.put(big_i, big_map.getOrDefault(big_i, 0)+1);
            big.poll();
        }
        
        while(big_map.getOrDefault(small.peek(), 0) > small_map.getOrDefault(small.peek(), 0)
        && !small.isEmpty())
        {
            int small_i = small.peek();
            small_map.put(small_i, small_map.getOrDefault(small_i, 0)+1);
            small.poll();
        }
    }
    
}
가장 쉬운 구현방법을 생각해보면 리스트를 선언하여 연산할 수 있겠지만, 그런 경우 시간이 굉장히 오래걸린다. 그래서 우선순위큐를 활용하여 문제를 풀어보자.

문제점은 우선순위큐에는 tail이라는 개념이 없는 것이다. 애초에 heap으로 구성이 되어 있으니 최대값만 찾거나 최소값만 찾을 수 있다. 필자는 이를 보완하기 위해 우선순위 큐 두개를 활용하기로 했다.

여기에 추가로 두 개의 맵을 선언하는데 맵의 역할은 각 큐에서 어느 숫자가 몇 번 삭제 되었는지 기록하는 용도이다. 우선순위 큐를 두개를 사용하였지만, 실제로는 하나의 큐로 인식하기 때문에 이 두 큐에서 한쪽만 원소가 삭제되면 안된다. 따라서 이 두 큐를 동기화하기 위해 사용된다.

첫 번째 for문을 보자. 일단 최대값을 제거해야 하는 경우 big에서 하나를 제거하고 맵에 삭제된 횟수를 갱신한다. 최솟값을 제거하는 경우도 동일한 원리로 작동한다.

만약 숫자를 삽입하는 경우라면 두 큐에 모두 삽입한다.

삭제 또는 추가를 마칠 때 마다, 동기화를 해야하는데 필자는 이를 synchronize라는 함수를 통해 구현하였다. 함수 내부를 들여다보면, 두 개의 while문이 나타나는데, 두 while문은 동작하는 방식이 동일하므로 첫번째 while문에 대해서 이야기하겠다.

big큐의 가장 첫번째 원소가 삭제된 횟수가 small에서 삭제된 횟수보다 작다면, 이는 지워야 하는 원소이므로 제거한다. big이 비어있지 않는 한 계속 반복하면 된다. 이를 통해 두 큐를 동기화 할 수 있다.

operation의 크기를 n이라 하였을 때, 최종 시간복잡도는 \(O(nlogn)\)이다. 그거보다 시간복잡도가 높지 않을까 생각하는 분이 계실 수도 있는데, 생각해보면 두 큐에 들어갔다 나오는 횟수를 전부 더하면 \(4nlogn\)이다.

테스트



질문하기를 보니까 조건에 부합하지 않게 짜도 통과되는 경우가 있다고 한다. 이 부분에서 좀 더 신경을 써줬으면 좋겠다.