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

📖 문제

프로그래머스

 

 

 

💡  풀이 방식

• Deque / LinkedList 활용

1. 명령어가 I인 경우, 리스트에 주어진 숫자를 삽입하고 오름차순 정렬시킨다.

2. 명령어가 D인 경우, 큐가 비어있다면 패스한다.

   큐가 비어있지 않고, 입력받은 수가 1인 경우 맨 뒤쪽 값(=최댓값)을 제거한다.

   큐가 비어있지 않고, 입력받은수가 -1인 경우 맨 앞쪽 값(=최솟값)을 제거한다.

 

3. 마지막에 큐가 비어있다면 (0, 0)을 출력한다.

큐가 비어있지 않다면, 큐에서 ( 맨 뒤쪽 값(=최댓값), 맨 앞쪽 값(=최솟값))을 출력한다.

 

 

🔺 코드

import java.util.*;
 
class Solution {
    public int[] solution(String[] operations) {        
        LinkedList<Integer> pq = new LinkedList<>();
        
        for(int i = 0 ; i < operations.length ; i++) {
            String[] s = operations[i].split(" ");
            
            String cmd = s[0];
            int num = Integer.parseInt(s[1]);
            
            if(cmd.equals("I")) {
                pq.add(num);
                Collections.sort(pq);   // 오름차순 정렬
            }
            else if(cmd.equals("D")) {
                if(pq.isEmpty())    continue;   // 빈 큐에서 데이터를 삭제하라는 연산인 경우, 무시
                
                if(num == 1)    pq.removeLast();
                else            pq.removeFirst();
            }            
        }
           
        // 출력하기
        int[] answer = new int[2];
        answer = pq.isEmpty() ? answer : new int[] {pq.pollLast(), pq.pollFirst()};
        return answer;
    }
}

 

 

 

➕ 다른 풀이 방식

대부분 최소 힙과 최대 힙을 각각 저장해 PriorityQueue를 2개 만드셔서 활용하셨다.

최소 힙은 오름차순 정렬, 최대 힙은 내림차순 정렬로 하게 하고.

PriorityQueue의 remove(Obejct o) 메소드를 활용해 중간에 있는 객체를 제거 가능하다.

maxQ.remove(minQ.poll());

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

---

🧐 새로 알게 된 내용

- PriorityQueue의 remove(Object o) 메소드는

객체가 존재한다면 삭제하고 true를 반환하지만, 객체가 존재하지 않는다면 false를 출력한다.

Java Tutorial - Java PriorityQueue.remove(Object o)

PriorityQueue remove() Method in Java - GeeksforGeeks

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

- Deque, LinkedList , ArrayDeque

Deque, LinkedList 와 ArrayDeque

 

- remove() 메소드 차이

: [PriorityQueue] boolean remove(Object o) / [ArrayList] E remove(int idx)

[자바] ArrayList와 Queue의 remove() 함수에 대해