[프로그래머스]힙(Heap):이중우선순위큐(java)

문제보러가기

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

이문제는 maxHeap큐와 minHeap큐를 이용해서 간단하게 풀 수 있었다. 진짜 어이없게도 큐에서 값을 제거할때 객체로 접근하여 해당하는 큐의 값을 제거하는게 되는지 까먹었다는... 후 열심히 해야겠다!

 

 

 

문제풀이

-maxHeap과 minHeap을 PriorityQueue 2개로 구현한다.

-주어진 배열에서 공백을 기준으로 split한 값을 배열에 넣는다.

-s[0]으로 D, I 를 구분하여 수행한다.

-I의 경우 maxHeap과 minHeap 둘다 add해준다.

-D 1일경우 maxHeap에서 poll하고 그 값으로 minHeap에서 찾아 remove해준다.

-D -1일경우는 위의 과정을 반대로 해준다.

 

 

import java.util.Collections;
import java.util.PriorityQueue;

public class Solution {

	public static void main(String[] args) {
		String[] operations = { "I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1" };//testcase
		//큐를 2개 생성한다.
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
		PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
		int[] answer = new int[2];
		for (int i = 0; i < operations.length; i++) {
        //공백을 기준으로 D,I를 파악한다.
			String[] s = operations[i].split(" ");
			if (s[0].equals("D") && !minHeap.isEmpty() && !maxHeap.isEmpty()) {
            //max값을 찾는지 min값을 찾는지 파악한다.
				if (s[1].equals("1")) {
					int max = maxHeap.poll();
					minHeap.remove(max);
				} else if (s[1].equals("-1")) {
					int min = minHeap.poll();
					maxHeap.remove(min);
				}
			}
			else if(s[0].equals("I")){
            //값을 두 큐에 모두 넣어준다.
				minHeap.add(Integer.parseInt(s[1]));
				maxHeap.add(Integer.parseInt(s[1]));				
			}

		}
		//큐가 비어있지 않을경우 max값과 min값을 찾는다.
		if(!minHeap.isEmpty()&&!maxHeap.isEmpty()){
			answer[0]=maxHeap.poll();
			answer[1]=minHeap.poll();
		}
        //큐가 비어있을경우 초기값인 [0,0]이 결과로 출력된다.
			System.out.println(answer[0]+" , "+answer[1]);
		
	}

}