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

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

• 이중우선순위큐

문제 설명

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

명령어수신 탑(높이)

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

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

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

입출력 예operationsreturn

["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]	[0,0]
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]	[333, -45]

 

(풀이코드)

import java.util.*;
class Solution {
    public int[] solution(String[] operations) {
	        int[] answer = {};
	        PriorityQueue<Integer> minq = new PriorityQueue<Integer>();
	        PriorityQueue<Integer> maxq = new PriorityQueue<Integer>(new Comparator<Integer>() {

				public int compare(Integer o1, Integer o2) {
					// TODO Auto-generated method stub
					return o2-o1;
				}
			});
	        for(String S : operations) {
	        	if(S.equals("D -1") ){
	        		maxq.remove(minq.poll());
	        	}else if(S.equals("D 1")) {
	        		minq.remove(maxq.poll());
	        	}else {
	        		int num = Integer.parseInt(S.split(" ")[1]);
	        		minq.add(num);
	        		maxq.add(num);
	        	}
	        }
	        if(minq.isEmpty()) {
	        	answer= new int[] {0,0};
	        }else {
	        	answer = new int[] {maxq.poll(), minq.poll()};
	        }
    	        return answer;
	    }
}

 

(코드설명)
이중우선순위 큐라고 해서 이중으로 두개의 큐를 선언해서 문제를 풀었다. 

우선 PriorityQueue를 선언하는 과정이다. minq는 최소값이 가장 우선순위에 있는 큐이고, 
maxq 는 가장 큰 값이 앞으로오도록, new Comparator를 선언하고, compare 값으로 순서를 변경해주었다. 

 

그리고 이제 반복문을 통해 주어진 문자열을 돌게 된다. 
문자열이 "D -1"이라면 최소값을 삭제해야한다.
 minq에서 poll을 통해 값을 없애면서 그 값을 maxq의 remove에 넣어 두 큐에서 모두 지워주었다.

문자열이 "D 1"인 경우도 마찬가지로 최대값을 지우기 위해서 
maxq에서 값을 poll() 해오면서, minq의 동일값도 remove로 지운다

밑의 값은 "I 숫자" 로 값이 들어온 경우이다. 
먼저 숫자만 분리하기 위해여 S.split으로 문자열을 자른 다음에 뒤에 있느 값만 Intege.parseInt()로 Int 값으로 변경하여 저장하였다. 
그리고 그 값을 minq와 maxq에 모두 넣어서 우선순위를 다시 설정해준다. 

위와 같은 값을 모두 돌면, minq와 maxq는 같은 size를 가지면서 우선순위는 다른 queue가 된든데, 

빈 값일 경우 큐에 수가 없을 경우 0,0 값을 return하라고 하였으므로, 
answer = new int[]{0,0}으로 선언해주었다. 

그리고 이제 빈값이 아닐경우, maxq의 가장 큰 값과 minq의 가장 작은 값을 
answer에 선언해주어 리턴한다. 

 

효율성은 이렇게 나온다.