[프로그래머스]Lv3.이중우선순위큐(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의 원소는 큐가 수행할 연산을 나타냄
  • 원소는 "명령어 데이터" 형식으로 주어집니다. 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

---

입출력 예 1

operations 

["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]

return

[0,0]

 

설명

16과 -5643을 삽입합니다 [16, -5643]

D -1이므로 최솟값을 삭제합니다 [16]

D 1이므로 최댓값을 삭제합니다  [ ]

D 1인데 아무것도 없으므로 무시합니다

I 123 이므로 123을 삽입합니다 [123]

D -1이므로 최솟값을 삭제합니다 [ ]

return 

빈 배열이기 때문에 [0,0]을 리턴

 

입출력 예 2

["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]

-45와 653을 삽입합니다. [-45, 653]

D 1이므로 최댓값을 삭제합니다 [-45]

-642, 45, 97값을 삽입합니다[-45, -642, 45, 97]

D 1이므로 최댓값을 삭제합니다 [-45, -642, 45]

D -1이므로 최솟값을 삭제합니다 [-45, 45]

333을 삽입합니다[-45, 45, 333]

return

최댓값, 최솟값 을 반환하므로 [333,-45]을 반환합니다.

 

---

첫번째 시도 

우선순위를 구해야하기 때문에 우선순위 큐인 PriorityBlockingQueue라는 것이 있다. FIFO과 다른 우선순위를 기준으로 동작합니다. 
우선순위 큐에 대해서는 자료구조 큐의 종류와 특징을 주제로 포스팅 해두었습니다!

트리 구조를 구현해야하는 구조입니다.

1. 최대, 최소 힙을 생성해야 합니다.
2. I 값 이라면 최대 최소 힙에 모두 삽입합니다.
3. D 1이라면 최대 힙에서 pop, D -1이면 최소 힙에서 poll
4. 3과 동시에 최대, 최소 힙에서도 동시에 해당 값을 삭제합니다.

import java.util.Collections; // 최대 힙 만들기 위해서 (reverseOrder()함수)
import java.util.PriorityQueue; // 우선순위 큐

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0,0};
        // PriorityQueue<Integer>은 우선순위가 높은게 작은 수인 것 기본
        PriorityQueue<Integer> heap = new PriorityQueue<Integer>(); // 최소 힙
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder()); // 최대 힙
        
        for (int i=0; i<operations.length; i++){ //operations값을 읽어올 반복문
            String st = operations[i].split(" ")[0]; // I인지 D인지 파악하기
            String num = operations[i].split(" ")[1]; // 값 확인
            int value = Integer.parseInt(num);
            System.out.println(value);
            
            // 경우의 수로 값을 추가, 삭제
            if (heap.size() < 1 && st.equals("D")){ // 힙에 값이 없고 D라면
                // 삭제할 수 있는 값이 없으므로 continue;
                continue;
            }
            if (st.equals("I")){ // 추가라면 최소, 최대 힙 모두 값 추가
                heap.offer(value);
                maxHeap.offer(value);
                continue;
            } 
            
            if (value < 0){ 
                // -1 : 최소 힙 poll()
                // 1 : 최대 힙 poll()
                // 1이면
                int min = heap.poll(); // 최소 힙에서 poll
                maxHeap.remove(min); // 해당 값을 삭제
                continue;
            }
            
            int max = maxHeap.poll(); //최대 힙에서 poll
            heap.remove(max); // 해당 값을 삭제
        }
                
        if(heap.size() > 0 ){
            
            answer[0] = maxHeap.poll();
            answer[1] = heap.poll();
            System.out.println(answer[0] + " , " + answer[1] );
        }
        
        return answer;
    }
    
    
}

 

 

 

 

 

참고

https://velog.io/@zayson/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Java-%EC%9D%B4%EC%A4%91-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90

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