프로그래머스 > 이중우선순위 큐

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어수신 탑(높이)

I 숫자	큐에 주어진 숫자를 삽입합니다.
D 1	큐에서 최댓값을 삭제합니다.
D -1	큐에서 최솟값을 삭제합니다.

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

 

 

List 를 만들어 요소를 Insert 할 때마다 정렬하고, 

최소값을 뺄 때는 List 의 맨 앞 요소를 removeFirst , 최대값을 뺄 때는 removeLast로 맨 뒤 요소를 제거한다.

	 public static int[] solution(String[] operations) {
        int[] answer = new int[2];
        LinkedList<Integer> list= new LinkedList<Integer>();
      
        for(int i=0;i<operations.length;i++) {
        	String order = operations[i];
        	if (order.startsWith("I")) {
        		String num = order.substring(order.indexOf(" ")+1);
        		int n = Integer.parseInt(num);
        		list.add(n);
        		Collections.sort(list);
        	} else if(order.startsWith("D")) { //양수는 최대값, 음수는 최소값 빼기 
        		if(list.size()>0) {
	        		String num = order.substring(order.indexOf(" ")+1);
	        		int n =Integer.parseInt(num);
	        		
	        		if ( n > 0 ) { // 1일때는
	        			list.removeLast();
	        		} else {
	        			list.removeFirst();
	        		}
        		}
        	}
        }
        
        if(list.size() > 0 ) {
        	answer[0] = list.pollLast();
        	
        } else {
        	answer[0] = 0;
        }
        if(list.size() > 0 ) {
        	answer[1] = list.pollFirst();
        } else {
        	answer[1] = 0;
        }
        
        return answer;
    }

다른사람의 풀이

max와 min que 를 각각 만들어 Insert 는 동시에 같이 하고 D 일 때 양수 음수에 따라 하나씩 어디서 뺄 지 결정한다.

Priority Que 이고 max 큐에는 reverseOrder 로 정렬을 적용한다.

D -1 최소값 제거시에는 min 큐에서 최소값을 빼고 max 큐에서도 제거한다.

예) [1, 2, 3]  에서 1을 poll , max 에서 1을 찾아 remove 

D 1 최대값 제거시에는 max 에서 최대값을 빼고 min 큐에서도 제거한다.  

 public int[] solution2(String[] arguments) {
	        PriorityQueue<Integer> max_q = new PriorityQueue<>(Collections.reverseOrder());
	        PriorityQueue<Integer> min_q = new PriorityQueue<Integer>();

	        for(int i=0; i<arguments.length; i++) {
	            StringTokenizer st = new StringTokenizer(arguments[i], " ");

	            while(st.hasMoreTokens()) {
	                String s = st.nextToken();
	                int max, min;
	                if("I".equals(s)) {
	                    int num = Integer.parseInt(st.nextToken());
	                    max_q.add(num);
	                    min_q.add(num);
	                } else if("D".equals(s)) {
	                    int num = Integer.parseInt(st.nextToken());
	                    if(max_q.size() == 0 || min_q.size() == 0) {
	                        continue;
	                    }
	                    if(num == -1) {
	                        min = min_q.poll();
	                        max_q.remove(min);
	                    } else if(num == 1) {
	                        max = max_q.poll();
	                        min_q.remove(max);
	                    }
	                }
	            }
	        }

	        int[] answer = new int[2];
	        if(max_q.isEmpty()) {
	            answer[0] = 0;
	        } else {
	            answer[0] = max_q.poll();
	        }
	        if(max_q.isEmpty()) {
	            answer[1] = 0;
	        } else {
	            answer[1] = min_q.poll();
	        }

	        return answer;
	    }