# \[99클럽 코테 스터디 10일차 TIL]  프로그래머스 - 이중우선순위큐

## \[level 3] 이중우선순위큐 - 42628

[문제 링크](https://school.programmers.co.kr/learn/courses/30/lessons/42628?language=java)

#### 구분

힙（Heap）

#### 문제 설명

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

| 명령어  | 수신 탑(높이)          |
| ---- | ----------------- |
| I 숫자 | 큐에 주어진 숫자를 삽입합니다. |
| D 1  | 큐에서 최댓값을 삭제합니다.   |
| D -1 | 큐에서 최솟값을 삭제합니다.   |

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

**제한사항**

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

**입출력 예**

| operations                                                                   | return      |
| ---------------------------------------------------------------------------- | ----------- |
| \["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]                  | \[0,0]      |
| \["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"] | \[333, -45] |

**입출력 예 설명**

입출력 예 #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]를 반환합니다.

***

## 풀이 코드

```java
import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = new int[2];
        PriorityQueue<Integer> asc = new PriorityQueue<>();
        PriorityQueue<Integer> desc = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int i = 0; i < operations.length; i++) {
            String[] s = operations[i].split(" ");
            String op = s[0];
            int num = Integer.parseInt(s[1]);
            if (op.equals("I")) {
                asc.offer(num);
                desc.offer(num);
            } else {
                if (desc.size() > 0 && num == 1) {
                    int d = desc.poll();
                    Iterator<Integer> it = asc.iterator();
                    while(it.hasNext()) {
                        if (it.next() == d) {
                            it.remove();
                            break;
                        }
                    }
                }
                if (asc.size() > 0 && num == -1) {
                    int a = asc.poll();
                    Iterator<Integer> it = desc.iterator();
                    while(it.hasNext()) {
                        if (it.next() == a) {
                            it.remove();
                            break;
                        }
                    }
                }
            }
        }
        if (desc.size() == 0) {
            return new int[]{0, 0};
        }
        answer[0] = desc.peek();
        answer[1] = asc.peek();
        return answer;
    }
}
```

* Time: 435.18 ms
* Memory: 149 MB

문제 제목부터 큰 힌트를 줘서 풀이가 어렵진 않았다. `PriorityQueue` 가 가지고 있는 메소드를 정확히 몰라서 Java 공식문서를 보긴 했다.

전에 LeetCode 에서 'Reorder Data in Log Files' 라는 문제의 풀이 방식이 생각나서 쉽게 풀 수 있었다. 해당 문제에서는 배열로 들어오는 문자열에 대해 문자 타입과 숫자 타입을 각각 구분하여 리스트에 담아서 푸는 문제였는데 그 덕분에 이중 우선순위 큐 문제를 보자마자 최솟값과 최댓값을 따로 담아야겠다는 생각을 할 수 있었다.

첫 풀이 때는 `PriorityQueue` 의 `removeIf()` 메소드가 생각나서 해당 메소드로 풀어보려 했는데 `removeIf(Predicate<? super E> filter)` 메소드로는 '최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.' 라는 제한사항을 충족할 수 없었다.

나중에 알았지만 `remove(Object o)` 함수를 사용하면 됐는데 풀 당시에는 몰라서 `iterator()` 메소드를 통해 해결했다. 아래는 `remove()` 함수를 적용하고 가독성을 조금 더 개선한 코드다.

### 개선하기

```java
import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        PriorityQueue<Integer> asc = new PriorityQueue<>();
        PriorityQueue<Integer> desc = new PriorityQueue<>(Collections.reverseOrder());

        for (String operation : operations) {
            if (operation.contains("I")) {
                int num = Integer.parseInt(operation.split(" ")[1]);
                asc.offer(num);
                desc.offer(num);
            }
            if (!desc.isEmpty() && operation.equals("D 1")) {
                asc.remove(desc.poll());
            }
            if (!asc.isEmpty() && operation.equals("D -1")) {
                desc.remove(asc.poll());
            }
        }
        if (desc.isEmpty() || asc.isEmpty()) {
            return new int[]{0, 0};
        }
        return new int[]{desc.peek(), asc.peek()};
    }
}
```

* Time: 69.92 ms
* Memory: 122 MB

속도 면에서도 훨씬 개선된 걸 확인할 수 있다.

***

## 돌아보기

IDE 없이 푸는걸 연습하고 있는데 확실히 여러 자료구조와 메소드를 외우게 되는 것 같다. 스스로 문제 풀이 방식은 생각나는데 메소드명이 기억나지 않으면 Java 공식 문서까지는 참고하자라고 생각해서 오늘 찾아보게 됐는데 이렇게 설명이 잘 작성되어 있었나 싶을 만큼 큰 도움이 돼서 왜 공식 문서로 공부하는게 좋다고 하는지 알았다.

### 다음에는

* 공식 문서를 봤으면 꼼꼼히 보기
* 공식 문서로 공부하기
* 조건식이나 반복문의 개선점을 차분히 생각하기

***

\#99클럽 #코딩테스트준비 #개발자취업 #항해99 #TIL


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://devlee.gitbook.io/docs/study/99/99-10-til.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.