[프로그래머스 / JAVA] 이중우선순위큐 Lv.3 풀이

문제

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

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때,

모든 연산을 처리한 후 큐가 비어 있으면 [0,0]

비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

 

제한 사항

operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.

operations의 원소는 큐가 수행할 연산을 나타냅니다.

 

원소는 "원소는 “명령어 데이터” 형식으로 주어집니다.

최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.

 

빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

입출력 예

 

풀이 과정

① 최대, 최소 Queue를 찾아야 하기때문에 PriorityQueue를 사용해야 하며

minHeap(최소 힙), maxHeap(최대 힙) 총 두개로 이중 Integer로 선언합니다.

② 반복문을 사용하여 split (" ")로 operations의 문자열을 잘라 배열 arrNum에 넣습니다.

③ if 조건문으로 만약 arrNum[0] (첫번째 명령어) 가 I 일때

minHeap과 maxHeap에 이중으로 arrNum[1] 의 값을 int로 형변환하여 넣습니다.

④ 같은 방법으로 명령어가 D 1 일때 최대 Heap이 비어있는지 확인하고 최대 Heap을 poll 명령을 사용하여 최댓값을 추출해서 remove 명령을 사용 후 minHeap 최댓값을 삭제합니다.

⑤ 4번과 같은 방법으로 D -1 일때 최소 Heap이 비어있는지 확인하고 최소 Heap을 poll 명령을 사용하여 최솟값을 추출해서 remove 명령을 사용 후 maxHeap 최솟값을 삭제합니다.

⑥ 출력할때는 최댓값, 최솟값이 나와야 하므로 배열 0, 1으로 answer[0] answer[1]을 각각 나눴습니다.

삼항연산자로 최대 Heap이 비어있으면 0을 출력 그렇지 않다면 peek()을 사용하여 최대 Heap 출력합니다.

최솟값도 동일하게 진행합니다.

 

전체 코드

import java.util.*;
class Solution {
	public static int[] solution(String[] operations) {

		PriorityQueue<Integer> minHeap = new PriorityQueue<>();
		PriorityQueue<Integer> maxHeap = new PriorityQueue<>(java.util.Collections.reverseOrder());

		for (String operation : operations) {
			String[] arrNum = operation.split(" ");

			if (arrNum[0].equals("I")) {
				minHeap.add(Integer.parseInt(arrNum[1]));
				maxHeap.add(Integer.parseInt(arrNum[1]));

			} else if (arrNum[0].equals("D") && arrNum[1].equals("1")) {
				if (!maxHeap.isEmpty()) {
					int maxValue = maxHeap.poll();
					minHeap.remove(maxValue);
				}
			} else if (arrNum[0].equals("D") && arrNum[1].equals("-1")) {
				if (!minHeap.isEmpty()) {
					int minValue = minHeap.poll();
					maxHeap.remove(minValue);
				}
			}
		}

		int[] answer = new int[2];
		answer[0] = maxHeap.isEmpty() ? 0 : maxHeap.peek();
		answer[1] = minHeap.isEmpty() ? 0 : minHeap.peek();

		return answer;
	}
}

 

결과