[프로그래머스] (Java) 이중우선순위큐 (힙/Heap)

 

🤖 1. 문제설명

문제 설명

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

 

 

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

 

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
• 원소는 “명령어 데이터” 형식으로 주어집니다.
• - 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

 

 

 

입출력 예 설명

 

입출력 예 #1

• 16과 -5643을 삽입합니다.
• 최솟값을 삭제합니다. -5643이 삭제되고 16이 남아있습니다.
• 최댓값을 삭제합니다. 16이 삭제되고 이중 우선순위 큐는 비어있습니다.
• 우선순위 큐가 비어있으므로 최댓값 삭제 연산이 무시됩니다.
• 123을 삽입합니다.
• 최솟값을 삭제합니다. 123이 삭제되고 이중 우선순위 큐는 비어있습니다.

따라서 [0, 0]을 반환합니다.

 

입출력 예 #2

• -45와 653을 삽입후 최댓값(653)을 삭제합니다. -45가 남아있습니다.
• -642, 45, 97을 삽입 후 최댓값(97), 최솟값(-642)을 삭제합니다. -45와 45가 남아있습니다.
• 333을 삽입합니다.

이중 우선순위 큐에 -45, 45, 333이 남아있으므로, [333, -45]를 반환합니다.

 

---

💡 2. 접근방식

 

Queue 를 이중으로 선언

문제 이름 그대로 max값을 꺼내올 큐와 min값을 꺼내올 큐를 두 개 선언

max큐는 내림차순 정렬, min큐는 오름차순 정렬 

 

operations의 요소를 순회하면서 " " 기준으로 `명령어`와 `값`으로 분리한다.

 

입출력 예

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

 

`I 16` :  숫자 `16`을 삽입(Insert 16)

`I -5643` :  숫자 `-5643`을 삽입(Insert -5643)

`D -1` :  최솟값 삭제(Delete min)

`D 1`: 최댓값 삭제(Delete max)

`D 1`: 최댓값 삭제(Delete max)

`I 123` :  숫자 `123`을 삽입(Insert 123)

`D -1` :  최솟값 삭제(Delete min)

 

각 operations[i] 값을 split(" ")으로 나누어 strs 배열에 저장하면

operations[0]인 "I 16" → strs = ["I", "16"]

operations[1]인 "I -5643" → strs = ["I", "-5643"]

이런 식으로 `strs[0]은 명령어`, `strs[1]은 값`으로 나뉘어 담기게 된다.

 

strs[0]이 "I" 이면 strs[1] 값을 두 큐에 담아주고,

strs[0]이 "D" && strs[1]이 1이면 max큐에서 최댓값을 빼내고

strs[0]이 "D" && strs[1]이 -1이면 min큐에서 최솟값을 빼낸다.

 

모든 과정이 끝나고 각 큐가 비었으면 0을 반환하고, 아니라면 최댓값과 최솟값을 반환한다.

 

---

생각보다 쉬운 코드인데 이게 난이도 3이나 된다고?

그리고 처음에 operations에서 I가 대문자 i인지 소문자 l인지 역슬래시 위에 있는 |인지 헷갈렸으나 insert이니까 대문자 I로 가정하고 코드를 썼더니 해결이 됐다. ㅎㅎㅎ

---

⭐ 3. 코드

역시 ㅋㅋㅋㅋㅋㅋㅋ.... 

왜 나는 첫번째 시도에서는 맨날 어떤 케이스는 맞고 어떤 케이스는 안맞는 것인가..

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        
        PriorityQueue<Integer> maxq = new PriorityQueue<>((o1, o2) -> (o2 - o1));
        PriorityQueue<Integer> minq = new PriorityQueue<>();
        
        for(int i = 0; i < operations.length; i++ ) {
            String[] strs = operations[i].split(" ");
            int num = Integer.parseInt(strs[1]);
            
            if(strs[0].equals("I")) {
                maxq.add(num);
                minq.add(num);
            } else if(strs[0].equals("D") && num==1) {
                minq.remove(maxq.poll());
            } else if(strs[0].equals("D") && num==-1) {
                maxq.remove(minq.poll());
            }
        }
        
        int min = minq.isEmpty()? 0 : minq.poll(),
            max = maxq.isEmpty()? 0 : maxq.poll();
        
        return new int[] {max, min};
    }
}

 

 

깔끔!

 

처음에 테스트 케이스 한 개만 통과됐던 이유는 return 할 때 min이랑 max 자리 바꿔써서 그런거였다. 테스트 케이스1은 값이 [0, 0] 이라 통과된거고, 위 코드처럼 {max, min}으로 바꿔주니까 바로 정답처리 됐다. int num 을 별도로 선언해 주기 전에는 코드가 길어지고 지저분했느다 Integer.parseInt(strs[1])로 미리 문자열을 형변환 해서 변수에 담아 주니까 코드가 훨씬 깔끔해졌다. 삼항연산자 써 준것도 깔끔~

 

 

🚀 프로그래머스에서  좋아요 많이 받은 코드

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

class Solution {
    public int[] solution(String[] arguments) {
        int[] answer = {0,0};

        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        PriorityQueue<Integer> reverse_pq = new PriorityQueue<Integer>(Collections.reverseOrder());

        for(int i=0; i<arguments.length; i++) {
            String temp[] = arguments[i].split(" ");
            switch(temp[0]) {
            case "I" : 
                pq.add(Integer.parseInt(temp[1]));
                reverse_pq.add(Integer.parseInt(temp[1]));
                break;
            case "D" :
                if(pq.size() > 0) {
                    if(Integer.parseInt(temp[1]) == 1) {
                        // 최댓값 삭제
                        int max = reverse_pq.poll();
                        pq.remove(max);
                    } else {
                        // 최솟값 삭제
                        int min = pq.poll();
                        reverse_pq.remove(min);
                    }
                }
                break;
            }
        }

        if(pq.size() >= 2) {
            answer[0] = reverse_pq.poll();
            answer[1] = pq.poll();
        }

        System.out.println(answer[0] + ":" + answer[1]);

        return answer;
    }
}

---

👉🏻 4. 같은 유형 문제 (우선순위큐)

[프로그래머스] (Java) 디스크컨트롤러 (힙/Heap) 우선순위 큐

[프로그래머스] (Java) 더 맵게 - 스코빌지수 (힙/Heap) Feat. 우선순위큐

[프로그래머스] (Java) 프로세스 문제풀이 (스택/큐)