오늘의 학습 내용
- 우선순위 큐
- 배열을 반환하는 방법
공부한 내용
-
우선순위 큐의 자료구조는 힙이다.
우선 순위 큐는 기본적으로PriorityQueue<Integer> pq = new PriorityQueue<>()이 형태로 작은 수가 우선적으로 정렬되는 자료구조이다. 그러나 큰 수를 우선적으로 정렬하고 싶은 경우에는PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder())이런 식으로 Collections 함수를 사용하거나PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b-a);이러한 comparator 메소드를 사용한다. -
특정 배열을 알고 있고 그 배열을 반환하는 방법은
new int[] {a,b}이다.
자바에서 배열을 반환할때new int[] {a,b}이런 식으로 명시를 해야 한다. 이는 배열 리터럴을 생성하기 위한 구문으로 특히 메서드에서 배열을 반환할때 사용한다. 이를 통해 배열의 크기와 초기값을 동시에 지정할 수 있다.
1)int[] arr = {a,b}
위 식은 배열을 선언하고 동시에 초기화하는 방식으로 초기에 선언할 때에만 사용할 수 있다.
2)int[] arr = new int[] {a,b}
배열을 선언할 때 뿐만 아니라 이미 선언된 배열 변수에 새 배열을 할당할 때도 사용할 수 있다.new int[]를 사용하여 배열 객체를 명시적으로 사용하고 배열을 반환할때 사용한다.
오늘의 회고
문제
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
명령어 수신 탑(높이)
- I 숫자 큐에 주어진 숫자를 삽입합니다.
- D 1 큐에서 최댓값을 삭제합니다.
- D -1 큐에서 최솟값을 삭제합니다.
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
제한사항
operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
operations의 원소는 큐가 수행할 연산을 나타냅니다.
원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
내 풀이
처음엔 우선순위 큐를 하나 이용해서 구현하려고 했는데 그런 식으로 한 경우 최소값과 최댓값을 동시에 알아내는 방법을 찾는게 어려웠다. 제목에서 힌트를 얻어 우선순위큐를 minHeap과 maxHeap을 이용했더니 답을 찾을 수 있었다.
operations 파라미터를 순차적으로 순회하면서 " "를 기준으로 자른다. 그러면 명령어는 chunk[0] 에 숫자는 chunk[1]에 들어가게된다. 이후 명령어에 따라 주어진 수식을 구현하면 된다.
package 프로그래머스;
import java.util.Collections;
import java.util.PriorityQueue;
public class 이중우선순위큐 {
public static int[] solution(String[] operations){
PriorityQueue<Integer> min = new PriorityQueue<>();
PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
for(int i=0; i<operations.length; i++){
String[] chunk = operations[i].split(" ");
int num = Integer.parseInt(chunk[1]);
switch (chunk[0]){
case "I" :
min.add(num);
max.add(num);
break;
case "D" :
if(max.isEmpty()) break;
if(num == 1){
int target = max.poll();
min.remove(target);
}
if(num == -1){
int target = min.poll();
max.remove(target);
}
}
}
if(max.isEmpty()){
return new int[] {0, 0};
}
return new int[] {max.peek(), min.peek()};
}
}
다른사람 풀이
최대한 함수를 나누는 방식이 재사용성에 좋아보였고 심지어 클래스로 분류하는게 한눈에 보인다.
import java.util.Collections;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
class Solution {
public int[] solution(String[] arguments) {
MidV q = new MidV();
for(int i = 0; i < arguments.length; i++){
String[] commend = arguments[i].split(" ");
int v = Integer.parseInt(commend[1]);
if(commend[0].equals("I")){
q.push(v);
}else{
switch (v){
case 1 : q.removeMax();
break;
case -1: q.removeMin();
break;
}
}
}
int[] aw = new int[]{q.getMaxValue(),q.getMinValue()};
return aw;
}
}
class MidV{
private PriorityQueue<Integer> leftHeap;
private PriorityQueue<Integer> rightHeap;
public MidV(){
leftHeap = new PriorityQueue<>(10,Collections.reverseOrder());//최대값;
rightHeap = new PriorityQueue<>();//최소값
}
public void push(int v){
leftHeap.add(v);
}
public void removeMax(){
while(!rightHeap.isEmpty()){
leftHeap.add(rightHeap.poll());
}
leftHeap.poll();
}
public void removeMin(){
while(!leftHeap.isEmpty()){
rightHeap.add(leftHeap.poll());
}
rightHeap.poll();
}
public int getMaxValue(){
if(leftHeap.size() == 0 && rightHeap.size() == 0)
return 0;
while(!rightHeap.isEmpty()){
leftHeap.add(rightHeap.poll());
}
return leftHeap.peek();
}
public int getMinValue(){
if(leftHeap.size() == 0 && rightHeap.size() == 0)
return 0;
while(!leftHeap.isEmpty()){
rightHeap.add(leftHeap.poll());
}
return rightHeap.peek();
}
}