체감 난이도 = 중하
https://school.programmers.co.kr/learn/courses/30/lessons/42628
문제 분석 및 설계
큐에서 최댓값과 최솟값을 구할 수 있어야합니다.
값이 새로 삽입된 후 그 안에서 최솟값이나 최댓값을 찾는 과정이 반복되기 때문에, 배열이나 리스트를 사용해서 값이 삽입될 때마다 새로 정렬하는것보다 힙을 사용하겠습니다.
그런데, 최댓값과 최솟값을 어떻게 하나의 힙에서 구할지가 고민됐습니다. 과연 힙을 사용하는게 적절할지 고민이 됐습니다.
하지만 다른 자료구조나 알고리즘(투포인터..)을 생각해봐도, 값이 새로 삽입될 때마다 매번 새로 정렬이 필요하기 때문에 적절하지 않다고 판단했습니다.
그렇다면 이제 힙 안에서 최댓값과 최솟값을 어떻게 구할지 고민했습니다. 우선순위 큐는 힙을 사용해서 구현하기때문에, 양쪽에서 값을 삽입 혹은 삭제할 수 없습니다. 따라서 저는 두 개의 큐를 이용해 최대값과 최솟값을 구했습니다.
제 설계는 최솟값을 삭제해야하는 상황에 최대큐에 값들이 있다면, 최대큐의 값들을 최소큐로 다 옮긴 후 최대큐를 비워줍니다. 따라서 삭제 명령어에서 최악의 경우에는 두 큐의 원소를 계속 옮겨주어야해서 시간복잡도가 괜찮을까 싶었습니다.
시간복잡도
큐가 비어있으면 삭제 명령어때 아무 일이 발생하지 않기때문에, 삭제 명령어에서 두 큐의 원소 옮기는 작업이 발생하려면 그만큼 사전에 삽입이 충분히 발생해야합니다.
따라서, operations의 총 길이 10^6에서 절반만큼 삽입이 발생했다고 가정하면, 10^3개의 원소를 10^3번 만큼 옮기는 작업이 일어날 것 입니다. 따라서 원소 옮기는 작업의 시간복잡도는 O(10^6)이 될 것입니다.
그리고 매번 큐를 옮기면 정렬이 발생하기 때문에, O(10^3 * log10^3)입니다.
따라서 총 (10^6 + 10^3log10^3)이라 시간복잡도가 괜찮을것이라 판단했습니다.
코드
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
int[] answer = new int[2];
Queue<Integer> minQ = new PriorityQueue<>();
Queue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
for (String str : operations) {
char c = str.charAt(0);
switch(c) {
case 'I' :
if (minQ.size() != 0) minQ.offer(Integer.parseInt(str.substring(2, str.length())));
else if (maxQ.size() != 0) maxQ.offer(Integer.parseInt(str.substring(2, str.length())));
else minQ.offer(Integer.parseInt(str.substring(2, str.length())));
break;
case 'D' :
if (minQ.size() == 0 && maxQ.size() == 0) break;
char i = str.charAt(2);
if (i == '1') {
if (minQ.size() != 0) {
maxQ.clear();
Iterator iter = minQ.iterator();
while (iter.hasNext()) {
maxQ.offer((Integer)(iter.next()));
}
}
minQ.clear();
maxQ.remove();
}
if (i == '-') {
if (maxQ.size() != 0) {
minQ.clear();
Iterator iter = maxQ.iterator();
while (iter.hasNext()) {
minQ.offer((Integer)(iter.next()));
}
}
maxQ.clear();
minQ.remove();
}
break;
}
}
if (minQ.size() != 0) {
answer[1] = minQ.remove();
while (minQ.size() >= 2) {
minQ.remove();
}
answer[0] = minQ.remove();
}
if (maxQ.size() != 0) {
answer[0] = maxQ.remove();
while (maxQ.size() >= 2) {
maxQ.remove();
}
answer[1] = maxQ.remove();
}
return answer;
}
}
코드 개선
우선순위 큐 두 개를 사용해서 구현하는것보다 좋은 방법이 있을까싶어 다른 사람 풀이를 둘러보던 중 제 코드에서 개선할 부분을 발견했습니다.
우선 대부분 사람들이 우선순위 큐 2개를 사용해서 구현했고, 이 부분에서 건드릴건 없는 것 같습니다.
remove()를 사용해서 우선순위 큐에서 특정 원소 값을 삭제할 수 있다는 사실을 알게되었습니다. 해당 메소드를 사용하면, 복잡하게 분기를 나눌 필요가 없어서 코드가 많이 간결해질 것 같습니다.
시간복잡도를 생각해보겠습니다. 중간의 값을 삭제하면 그만큼 새로 정렬이 발생합니다. 그런데 이전 방식에서 어차피 삭제 명령어 수행시 큐의 원소를 옮기는 작업이 발생하고 이때 힙 정렬이 일어나기 때문에, 개선한 방법이나 이전 방법이나 시간복잡도는 비슷할것이라 판단했습니다.
import java.util.*;
class Solution {
public int[] solution(String[] operations) {
int[] answer = new int[2];
Queue<Integer> minQ = new PriorityQueue<>();
Queue<Integer> maxQ = new PriorityQueue<>(Collections.reverseOrder());
for (String str : operations) {
char c = str.charAt(0);
switch(c) {
case 'I' :
minQ.offer(Integer.parseInt(str.substring(2, str.length())));
maxQ.offer(Integer.parseInt(str.substring(2, str.length())));
break;
case 'D' :
if (minQ.size() == 0 && maxQ.size() == 0) break;
char i = str.charAt(2);
if (i == '1') {
minQ.remove(maxQ.remove());
}
if (i == '-') {
maxQ.remove(minQ.remove());
}
break;
}
}
if (minQ.size() != 0 || maxQ.size() != 0) {
answer[0] = maxQ.remove();
answer[1] = minQ.remove();
}
return answer;
}
}
공부한 사항
-
우선순위 큐 활용 상황 : 반복적으로 최댓값 혹은 최솟값을 찾아야 하는 경우
반복마다 최적의 값, 즉 최댓값 혹은 최솟값을 찾아야 하는 상황에서 억지로 모든 데이터에 대해서 정렬을 하는 것은 매우 소모적인 행위이기때문에, 이럴때 heap을 통해 우선순위 큐를 구현해서 최댓값 혹은 최솟값만을 얻을 수 있으면 빠르게 문제를 해결할 수 있습니다.
만약 새로운 값을 삽입한 후 정렬이 필요한 경우가 아니라면, 기존 배열을 정렬하는게 좋다. -
우선순위 큐 모든 값 출력
Iterator iterator = pq.iterator();
while(iterator.hasNext()) System.out.print(iterator.next() + " ");- 우선순위 큐의 특정 값 삭제
remove(Object o) : o 제거
