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

문제출처 : programmers.co.kr/learn/courses/30/lessons/42628

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

풀이법:

1) Max Heap, Min Heap을 하나 씩 만든다.

2) Insert 할 때는 Max Heap, Min Heap 두 개에 모두 넣는다.

3) 이 두 힙의 내용물을 일치 시키는게 문제의 핵심이다.

    해시맵 visited를 만들어서 'D' 명령어를 만날 때 처음 push 하는 값이 나올때 까지 각 max, min 힙에서 push 하게 한다.

    구분 하는 법은 처음 입력의 index로 고유식별자(?) 를 붙여서 큐에 insert 하면 된다. 해쉬맵에선 이 index를 저장하고.

   

Comment:

1) 풀이법을 쉽게 생각해낼 수 있었다. dfs 문제를 다룬 경험에서 visited에 대한 경험이 바로 생각났다.

2) 한 큐에 코드를 쭉 작성할 수 있었다. 머리가 잘 돌아가는 날 인가보다.

3) visited를 HashMap으로 하면 이제 앞으로 무조건 O(1)이 걸리지 않을까? 문제를 풀면서 갑자기 떠오른 생각이다. (이전 까지는 array로 했었다)

 

코드:

import java.util.*;

public class Element implements Comparable<Element>{

	int num;
	int index;
	
	public Element(int num, int index) {
		this.num = num;
		this.index = index;
		
	}

	@Override
	public int compareTo(Element target) {
		// TODO Auto-generated method stub
		
		if(this.num < target.num) {
			return -1;
		}else if(this.num > target.num) {
			return 1;
		}else{
			return 0;
		}
	}
}
class Solution {
    public static PriorityQueue max_pq;
	public static PriorityQueue min_pq;
	public static HashMap<Integer, Integer> visited;
    
    public int[] solution(String[] operations) {
        int[] answer = {};
        
        max_pq = new PriorityQueue(Comparator.reverseOrder());
		min_pq = new PriorityQueue();
		visited = new HashMap();
        
		for(int i = 0; i < operations.length; i++) {
			String command = operations[i];
			handleCommand(command, i);
		}       
		
		if(max_pq.isEmpty() || min_pq.isEmpty()) {
			int[] temp = {0, 0};
            answer = temp;
		}else {
			Element min = deQueue(min_pq);
			Element max = deQueue(max_pq);
			
            int[] temp = {max.num, min.num};
            answer = temp;
		}
        return answer;
        
    }
    
	public static void handleCommand(String com, int index) {
		
		char[] seq = com.toCharArray();
		char comType = seq[0];
		StringBuilder tmpNum = new StringBuilder();
		int num;
		
		//negative number
		if(seq[2] == '-') {
			for(int i = 3; i < seq.length; i++) {
				tmpNum.append(seq[i]);
			}
			num = -1 * Integer.parseInt(tmpNum.toString());
			
		}else {
			
			for(int i = 2; i < seq.length; i++) {
				tmpNum.append(seq[i]);
			}
			
			num = Integer.parseInt(tmpNum.toString());
		}
		
		if(comType == 'I') { //insert

			Element el = new Element(num, index);
			
			max_pq.add(el);
			min_pq.add(el);
			
		}else if(comType == 'D') { //delete
			
			if(num == 1) { //delete max value
				deQueue(max_pq);
				}else if(num == -1){ //delete min value
				deQueue(min_pq);
				}
			}
				
		
	
	}

	public static Element deQueue(PriorityQueue pq) {

		Element el = new Element(-1,-1);
		
		while(!pq.isEmpty()) {
			Element temp = (Element)pq.peek();
			int tempIdx = temp.index;
			
			if(visited.containsKey(tempIdx)) {
				el = (Element) pq.poll();
			}else {
				el = (Element) pq.poll();
				visited.put(tempIdx, 0);
				break;
			}
			
		}
		
		return el;
		
	}    
}