프로그래머스-이중우선순위큐[자바]

문제

답

import java.util.PriorityQueue;
import java.util.Collections;

class Solution {
    public int[] solution(String[] operations) {
        
        PriorityQueue<Integer> minQue = new PriorityQueue<>();
        PriorityQueue<Integer> maxQue = new PriorityQueue<>(Collections.reverseOrder());
        
        for(String operation : operations) {
            String op = operation.split(" ")[0];
            int num = Integer.parseInt(operation.split(" ")[1]);
   
            if("I".equals(op)) {
                minQue.add(num);
                maxQue.add(num);
            }
            else if("D".equals(op)) {
                if(maxQue.isEmpty()) continue;
                if(num == 1) {
                    int del = maxQue.poll();
                    minQue.remove(del);
                } else if(num == -1) {
                    int del = minQue.poll();
                    maxQue.remove(del);
                }
            }
         
        }
        if(maxQue.isEmpty()) return new int[] {0,0};
        return new int[] {maxQue.peek(), minQue.peek()};
    }
}

---

이 문제는 PriorityQueue를 사용하면 간단하게 해결할 수 있다...고 한다
이중우선순위큐를 처음 들어봐서 이번 기회에 공부하고 간단하게 정리해본다

1. PriorityQueue란

• 일반적인 큐는 FIFO 형식의 자료구조이지만 우선순위 큐는 우선순위가 높은 데이터가 먼저 나가는 자료구조 형태이다. 우선순위 큐의 경우 힙 자료구조 등을 통해 구현 가능하다

2. PriorityQueue 선언 방법

// 기본형: 우선선위가 낮은 숫자가 먼저 나옴
PriorityQueue<Integer> pQ = new PriorityQueue<>();

// 우선선위가 높은 숫자가 먼저 나옴
PriorityQueue<Integer> pQ = new PriorityQueue<>(Collections.reverseOrder());

3. 기본적인 메서드

• add() : 원소 추가. 큐가 꽉 찬 경우 에러 발생
• offer() : 원소 추가. 값 추가 실패시 false 반환
• poll() : 첫 번째 값을 반환하고 제거. 비어있으면 null반환
• remove() : 첫 번째 값을 반환하고 제거. 비어있으면 에러 발생
• isEmpty() : 첫 번째 값을 반환하고 제거. 비어있으면 에러 발생.
• clear() : 초기화
• size() : 원소의 수 반환

4. 기본적인 사용법

import java.util.PriorityQueue;

public class Example {
	public static void main(String[] args) {
    	PriorityQueue<Integer> pQ = new PriorityQueue<>();
        
        pQ.offer(1);
        pQ.offer(6);
        pQ.offer(2);
        
        while(!pQ.isEmpty()) {
        	System.out.println("pQ.poll() = " + pQ.poll());
        }
    }
}

5. PriorityQueue 클래스의 객체 우선순위 정의

• 이건 Comparator클래스를 overide하면 된다!

import java.util.Comparator;
import java.util.PriorityQueue;

class Student {
	int mathScore;
    int engScore;
    
    public Student(int mathScore, int engScore) {
    	this.mathScore = mathScore;
        this.engScore = engScore;
    }
}

class StudentComparator implements Comparator<Student> {
	@Override
    public int compare(Student o1, Student o2) {
    	if(o1.mathScore == o2.mathScore) {
        	return o2.engScore - o1.engScore;
        } else {
        	return o1.mathScore - o2.mathScore;
        }
    }
}

public class Example {
	public static void main(String[] args) {
    	PriorityQueue<Student> pQ = new PriorityQueue<>(1, new StudentComparator());
        pQ.offer(new Student(70, 50));
        pQ.offer(new Student(60, 40));
        pQ.offer(new Student(70, 40));
        
        while(!pQ.isEmpty()) {
        	Student s = pQ.poll();
            System.out.printf("Student\'s MathScore and engScore: %d, %d \n", s.mathScore, s.engScore); 
        }
    }
}

출처 : https://kbj96.tistory.com/49