[알고리즘] 이중우선순위큐 (프로그래머스 Level3)

코딩테스트 연습 - 이중우선순위큐

 기본적으로 우선순위큐는 Heap을 통해서 구현된다. 하지만 자바에는 기본적으로 PriorityQueue가 구현이 되어있으므로 우선순위큐 자체에는 신경쓸 필요가 없고, 이중우선순위큐라는 점에 주목해야한다.

 이 말인 즉슨, 한 큐에서 최대값을 반환, 최소값을 반환하는 두 가지 작업이 동시에 가능해야된다는 점이다.

 

Solution

 우선 각각 최대값, 최소값을 반환하는 PriorityQueue 2개를 만들었다. 하지만 데이터를 삭제할 때, 2개의 큐를 모두 동기화시킬 필요가 있다. 때문에 HashMap을 사용했다.

 HashMap의 Key값은 삽입된 데이터, Value는 현재 큐에 들어있는 해당 데이터의 개수를 의미한다.

 

 이 후에 삽입 때는 특별한 작업없이 바로 2개의 큐와 HashMap에 삽입하고 개수 카운팅을 1씩 올려준다.

 

 다만 삭제할 때는, 현재 dequeue한 데이터가 0개인 데이터들을 모두 삭제하고 적어도 1개 이상 남아있는 데이터를 만날 때까지 dequeue를 반복한다.

 

 그리고 마지막 결과값을 반환할 때는, HashMap, 최대 우선순위큐, 최소 우선순위큐 중 하나라도 비어있다면 [0, 0]을 반환한다.

 나머지 경우에는 아까와 마찬가지로 데이터를 계속 dequeue해서 현재 개수가 1개 이상인 데이터를 만나면 그 값을 반환한다.

import java.util.*;


class Solution {

	HashMap<Integer, Integer> map = new HashMap<>();

	public int[] solution(String[] operations) {
		int[] answer = new int[2];

		PriorityQueue<Integer> min_heap = new PriorityQueue<>();
		PriorityQueue<Integer> max_heap = new PriorityQueue<>(new Comparator<Integer>() {
			@Override
			public int compare(Integer o1, Integer o2) {
				return o2 - o1;
			}
		});


		for(int i = 0;i < operations.length;i++)
		{
			String[] list = operations[i].split(" ");

			//삽입
			if(list[0].equals("I"))
			{
				int key = Integer.parseInt(list[1]);
				min_heap.offer(key);
				max_heap.offer(key);

				map.putIfAbsent(key, 0);
				map.computeIfPresent(key, (k, v) -> ++v);
			}
			else
			{
				if(!map.isEmpty())
				{
					//최대값 빼내기
					if(list[1].equals("1"))
					{
						while(!max_heap.isEmpty() && map.get(max_heap.peek()) < 1)
							max_heap.poll();

						if(!max_heap.isEmpty())
						{
							map.computeIfPresent(max_heap.peek(), (k, v) -> --v);
							max_heap.poll();
						}
					}
					//최소값 빼내기
					else if(list[1].equals("-1"))
					{
						while(!min_heap.isEmpty() && map.get(min_heap.peek()) < 1)
							min_heap.poll();

						if(!min_heap.isEmpty())
						{
							map.computeIfPresent(min_heap.peek(), (k, v) -> --v);
							min_heap.poll();
						}
					}
				}

			}
		}

		if(map.isEmpty() || max_heap.isEmpty() || min_heap.isEmpty())
		{
			answer[0] = 0;
			answer[1] = 0;
		}
		else
		{
			while(!max_heap.isEmpty() && map.get(max_heap.peek()) == 0)
				max_heap.poll();
			answer[0] = max_heap.poll();
			
			while(!min_heap.isEmpty() && map.get(min_heap.peek()) == 0)
				min_heap.poll();
			answer[1] = min_heap.poll();
		}

		return answer;
	}
}