- Published on
- •👁️
이중우선순위큐
- Authors
- Name
- River
문제 설명
이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.
| 명령어 | 수신 탑(높이) |
|---|---|
| I 숫자 | 큐에 주어진 숫자를 삽입합니다. |
| D 1 | 큐에서 최댓값을 삭제합니다. |
| D -1 | 큐에서 최솟값을 삭제합니다. |
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.
제한사항
- operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
- operations의 원소는 큐가 수행할 연산을 나타냅니다.
- 원소는 "명령어 데이터" 형식으로 주어집니다.
- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
- 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.
입출력 예
입력
["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]
출력
[0,0]
설명
16과 -5643을 삽입합니다. 최솟값을 삭제합니다. -5643이 삭제되고 16이 남아있습니다. 최댓값을 삭제합니다. 16이 삭제되고 이중 우선순위 큐는 비어있습니다. 우선순위 큐가 비어있으므로 최댓값 삭제 연산이 무시됩니다. 123을 삽입합니다. 최솟값을 삭제합니다. 123이 삭제되고 이중 우선순위 큐는 비어있습니다. 따라서 [0, 0]을 반환합니다.
입력
["I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"]
출력
[333, -45]
설명
-45와 653을 삽입후 최댓값(653)을 삭제합니다. -45가 남아있습니다. -642, 45, 97을 삽입 후 최댓값(97), 최솟값(-642)을 삭제합니다. -45와 45가 남아있습니다. 333을 삽입합니다. 이중 우선순위 큐에 -45, 45, 333이 남아있으므로, [333, -45]를 반환합니다.
풀이 접근법
시간복잡도 : O(N log N)
공간복잡도 : O(N)
사용 알고리즘 :
그리디트리맵
핵심 포인트 :
- TreeMap을 사용하여 최댓값과 최솟값을 O(log N)에 찾기
- 중복 값 처리를 위해 key-value 쌍으로 개수 관리
- 삭제 시 개수가 1이면 key 제거, 1 초과이면 개수만 감소
경계값/반례 :
- 중복 값이 있는 경우 하나씩만 삭제
- 빈 큐에서 삭제 연산이 주어지는 경우
핵심 아이디어
- TreeMap을 사용하여 최댓값과 최솟값을 효율적으로 관리
- TreeMap의
firstKey()와lastKey()로 O(log N) 시간에 최솟값, 최댓값 접근 - 중복 값 처리를 위해 key는 값, value는 개수로 관리
- 삭제 시 개수를 확인하여 적절히 처리
해결 방법
- TreeMap을 사용하여 값과 개수를 key-value로 관리
- 삽입 시 기존 개수에 1을 더해서 저장
- 최댓값 삭제 시
lastKey()를 사용하여 가장 큰 값의 개수 감소 - 최솟값 삭제 시
firstKey()를 사용하여 가장 작은 값의 개수 감소 - 개수가 1이면 key를 제거하고, 1 초과이면 개수만 감소
핵심 패턴
1️⃣ TreeMap을 이용한 이중 우선순위 큐
TreeMap<Integer, Integer> tm = new TreeMap<>();
// 삽입: 기존 개수에 1 추가
tm.put(value, tm.getOrDefault(value, 0) + 1);
// 최댓값/최솟값 접근
tm.lastKey(); // 최댓값
tm.firstKey(); // 최솟값
- TreeMap은 자동으로 key를 정렬하여 관리
firstKey()와lastKey()로 O(log N) 시간에 최솟값, 최댓값 접근
2️⃣ 중복 값 처리
int count = tm.get(tm.lastKey());
if (count == 1) {
tm.remove(tm.lastKey());
} else {
tm.put(tm.lastKey(), count - 1);
}
- 개수가 1이면 key 자체를 제거
- 개수가 1 초과이면 개수만 1 감소
3️⃣ 빈 큐 처리
if (!tm.isEmpty()) {
// 삭제 연산 수행
}
- 빈 큐에서의 삭제 연산은 무시
1차 제출 코드 ⭕
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
int[] answer = {0, 0};
TreeMap<Integer, Integer> tm = new TreeMap<>();
for (String operation : operations) {
String[] action = operation.split(" ");
if (action[0].equals("I")) {
Integer value = Integer.valueOf(action[1]);
tm.put(value, value); // ❌ 중복 값 처리 불가
} else if (action[0].equals("D") && action[1].equals("1")) {
if (!tm.isEmpty()) tm.remove(tm.lastKey());
} else {
if (!tm.isEmpty()) tm.remove(tm.firstKey());
}
}
if (!tm.isEmpty()) {
return new int[] {tm.lastKey(), tm.firstKey()};
}
return answer;
}
}
테스트 케이스 추가
- 프로그래머스에서 제출 통과는 했지만 아래의 테스트 케이스를 추가하면 코드 실행 시 틀린다.
- 테스트 케이스 추가:
operations = ["I 10", "I 10", "I 20", "D 1", "D 1"] - "최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다"라고 언급이 되어 있다. 즉, 10이 2번 들어왔을 때 그냥 TreeMap을 사용하면 중복값으로 제거되기 때문에 최댓값/최솟값이 둘 이상인 경우는 존재할 수 없다.
최종 제출 코드
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
int[] answer = {0, 0};
TreeMap<Integer, Integer> tm = new TreeMap<>();
for (String operation : operations) {
String[] action = operation.split(" ");
if (action[0].equals("I")) {
Integer value = Integer.valueOf(action[1]);
tm.put(value, tm.getOrDefault(value, 0) + 1); // ✅ 개수로 관리
} else if (action[0].equals("D") && action[1].equals("1")) {
if (!tm.isEmpty()) {
int count = tm.get(tm.lastKey());
if (count == 1) {
tm.remove(tm.lastKey());
} else {
tm.put(tm.lastKey(), count - 1);
}
}
} else {
if (!tm.isEmpty()) {
int count = tm.get(tm.firstKey());
if (count == 1) {
tm.remove(tm.firstKey());
} else {
tm.put(tm.firstKey(), count - 1);
}
}
}
}
if (!tm.isEmpty()) {
return new int[] {tm.lastKey(), tm.firstKey()};
}
return answer;
}
}