참고
문제해설
문제 로직고민
NOTE
•
우선순위 큐를 활용해서 최대 값, 최소 값을 동시에 뽑아내야 한다.
◦
우선순위큐는 Heap구조로 최대 값, 또는 최소 값에 대한 구조로만 가질 수 있다.
◦
완전히 정렬된 상태의 배열도 생각해보았지만 추가과정에서의 연산이 많아질것같다.
•
2개의 최대, 최소 우선순위큐를 사용한다?
◦
그러면 최대값을 뽑아냈을때 최소에서 어떻게 제거해주는가?
◦
단순히 검색해서 제거하는건 비효율적일것이다.
작성코드
NOTE
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
PriorityQueue<Integer> minPq = new PriorityQueue<Integer>();
PriorityQueue<Integer> maxPq = new PriorityQueue<Integer>(Collections.reverseOrder());
for(String s : operations){
String[] temp = s.split(" ");
String op = temp[0];
int value = Integer.parseInt(temp[1]);
if(op.equals("I")){
minPq.offer(value);
maxPq.offer(value);
}
if(maxPq.isEmpty() || minPq.isEmpty()) continue;
if(op.equals("D") && value == 1){
int max = maxPq.poll();
minPq.remove(max);
}
if(op.equals("D") && value == -1){
int min = minPq.poll();
maxPq.remove(min);
}
}
int[] answer = new int[2];
if(!minPq.isEmpty() && !maxPq.isEmpty()){
answer[0] = maxPq.poll();
answer[1] = minPq.poll();
}
return answer;
}
}
Java
복사
그냥 remove하는게 비효율적이라 생각했는데 통과는 되었다.
다른사람 풀이
NOTE
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int T = Integer.parseInt(br.readLine());
while(T-- > 0) {
TreeMap<Integer, Integer> treeMap = new TreeMap<>();
int n = Integer.parseInt(br.readLine());
T
while(n-- > 0) {
st = new StringTokenizer(br.readLine());
String str = st.nextToken();
int num = Integer.parseInt(st.nextToken());
switch(str) {
case "I" :
treeMap.put(num, treeMap.getOrDefault(num, 0) + 1);
break;
case "D" :
if(treeMap.isEmpty()) break;
if(num == -1) {
int minKey = treeMap.firstKey();
if(treeMap.get(minKey) == 1) {
treeMap.remove(minKey);
}else {
treeMap.put(minKey, treeMap.get(minKey) - 1);
}
}else {
int maxKey = treeMap.lastKey();
if(treeMap.get(maxKey) == 1) {
treeMap.remove(maxKey);
}else {
treeMap.put(maxKey, treeMap.get(maxKey) - 1);
}
}
break;
}
}
if(treeMap.isEmpty()) {
sb.append("EMPTY\n");
}else {
sb.append(treeMap.lastKey() + " " + treeMap.firstKey() + "\n");
}
}
System.out.println(sb.toString());
}
}
Java
복사
더 효율적인 코드
•
사실 이 코드는 프로그래머스 문제가아니라 백준의 이중 우선순위 큐를 가져온 코드이다.
•
TreeMap의 경우 Red-Black Tree로 구성되며, Key를 기준으로 자동 정렬되므로 더 효율적으로 이루어질 수 있다.
◦
pq를 사용할시 remove 연산으로 인해 O(n)의 시간 복잡도가 추가됨
◦
red-black을 사용할시 전체연산이 O(log n)의 시간 복잡도로 계산됨