[Java] 우선순위 큐 개념정리 - 프로그래머스 이중우선순위큐 문제풀이

우선순위 큐가 뭘까 🤔?

 

• priority queue는 힙이라고도 한다.
• 특정 원소 중에서 최대 우선순위를 가지는 값을 효율적으로 구하려고 고안된 자료구조이다.
• 우선순위 큐에서는 최대 우선순위 값 이외의 원소는 알 수 없다.
• 내부적으로 이진 트리를 사용한다.
  • 우선순위 큐 내의 원소의 개수를 N이라고 했을 때, 원소 삽입과 최대 우선순위 값 뽑기 두 연산을 모두 O(logN)의 시간복잡도를 가진다. (빠르다!)

 

우선 순위 큐를 사용해보자

 

• 먼저 무작위로 섞여 있는 원소들은 모두 우선순위 큐에 넣는다.
• 최대 우선순위 값을 계속해서 뽑으면 원소가 정렬되고 시간복잡도가 O(N logN)이 됨 → 힙 정렬
• 자바에서는 java.util 패키지의 PriorityQueue<E> 제네릭 클래스를 사용한다.
  • add() : 원소를 삽입한다.
  • poll() : 최대 우선순위 값을 뽑힌다.
• 예를들어, {4,2,6,1} 순으로 삽입하면 뽑을때는 {1,2,4,6} 순서로 나옴 → 기본적으로 작은 값일수록 우선순위가 높다!!
• 이러한 기준은 Comparator를 생성자에 넣고 직접 설정 가능하다.
• 내림차순으로 정렬하고 싶다면 Comparator사용해서 큰값일수록 높은 우선순위를 가지도록 설정할 수 있다.

 

PriorityQueue<Integer> pq = new PriorityQueue<>( (a,b) -> b-a );

 

• 우선순위 큐는 시간복잡도가 O(lonN)으로 짧다.
  • 우선순위가 높은 원소를 뽑을 수 있기 때문에 최댓값 or 최솟값처럼 우선순위에 따라 작업을 처리할 경우 유용하다.

 

---

 

문제) 프로그래머스 - 이중 우선순위 큐 (lv.3)

 

문제 설명

 

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

 

명령어	수신 탑(높이)
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]를 반환합니다.

 

---

문제 풀이)

 

어떤 알고리즘을 선택해야할까? 🤔

 

• 주어진 숫자 중에서 최댓값과 최솟값을 계속해서 찾아야 한다. → 우선순위 큐를 선택!
• 2개의 우선순위 큐를 사용해서 최댓값과 최솟값 모두를 찾아낼 수 있다.

 

그런데 첫번째 문제가 발생했다! 🤔

 

문제 상황1) 최댓값 큐에서 최댓값을 삭제했을 경우, 최솟값 큐에서는 해당 값을 삭제할 수 없다.

두 개의 큐가 진행상황을 공유하지 못하기 때문에 두개다 비워졌는지 확인을 하기가 어렵다!

 

 

해결하려면?

관리 중인 값의 개수를 별도로 관리하면
이중 큐가 실제로 비워져있는지를 확인할 수 있다.

 

 

큐에 원소를 추가할때는 관리 중인 값의 개수에  +1, 원소를 삭제할때는 -1를 해주자.

만약 관리 중인 값의 개수가 0이되면 두개의 우선순위 큐가 비어있다는 것으로 이해할 수 있다.

 

 

 

---

 

그런데 두번째 문제가 발생했다! 🤔

 

이중 큐에 원소를 여러번 추가하고, 추가한만큼 최댓값 삭제도 반복하면 어떻게 될까?

추가한 만큼 삭제를 시도했기때문에 이중 큐는 비워져있는 상태가 되어야한다.

 

하지만 실제로는 최댓값 큐에서만 원소가 삭제되고, 최솟값 큐는 그대로 원소를 가지게된다.

문제상황 2) 최댓값을 관리하는 우선순위 큐는 비워져있지만 최솟값을 관리하는 우선순위 큐는 추가된 값을 모두 원소로 가지고 있다.

이렇게 된다면 최솟값 큐와 최댓값 큐의 내부 원소가 다르기 때문에 최댓값/최솟값을 뽑을 때 오해가 발생할 수 있다.

 

 

이런 경우에는 관리하는 원소의 개수가 0일때
최댓값 큐와 최솟값 큐를 모두 비워준 후 오해를 없애자!

 

이중큐가 비워져있어야할 때 원소가 들어있는 것이 문제이기 때문에

원소의 개수가 0이 되면 최댓값 큐와 최솟값 큐를 모두 비워주면 오해를 없앨 수 있을 것이다.

 

 

 

위의 내용을 토대로 최댓값을 관리하는 큐와 최솟값을 관리하는 큐, 원소의 개수를 저장하는 변수가 필요하다는 것을 알게 되었다.

 

---

문제 풀이를 토대로 로직 구현하기

 

DoublyPriorityQueue 클래스 생성하기

 

나는 DoublyPriorityQueue 클래스를 생성해서 3가지 속성들을 관리하려한다.

• size : 원소 개수
• minPq : 최솟값 관리하는 우선순위 큐
• maxPq : 최댓값 관리하는 우선순위 큐

 

private static class DoublyPriorityQueue {
	private int size = 0;
	private PriorityQueue<Integer> minPq = new PriorityQueue<>();
	private PriorityQueue<Integer> maxPq = new PriorityQueue<>( (a,b) -> b-a);
}

 

 

이중 큐에 원소를 삽입

 

이중 큐에 원소를 삽입하는 부분을 구현해보자. 최댓값 큐와 최솟값 큐에 각각 원소를 넣어주어야 하고, 원소의 개수인 size도 +1 해주어야 한다.

 

public void add(int value){
	minPq.add(value);
	maxPq.add(value);
	size++;
}

 

 

최댓값을 제거

 

다음은 최댓값을 제거하는 것을 구현해보자. 최댓값 큐에서 원소를 삭제해서 구현할 수 있다. 만약 원소개수가 0이라면 두개의 큐 모두를 비워줘야한다.

 

public void removeMax(){
	if(size==0) return;
	maxPq.poll();
	if(--size == 0){
		maxPq.clear();
		minPq.clear();
	}
}

 

 

최솟값을 제거

 

최솟값을 삭제하는 것도 동일하다.

 

public void removeMin(){
	if(size==0) return;
	minPq.poll();
	if(--size==0){
		maxPq.clear();
		minPq.clear();
	}
}

 

 

최댓값/최솟값을 반환

 

이제 문제를 풀기위해 이중순위큐에서 최댓값과 최솟값을 구하는 로직을 만들자.

최댓값은 최댓값 큐에서, 최솟값은 최솟값 큐에서 원소를 꺼내면 된다.

 

public int max(){
	if(size==0) return 0;
	return maxPq.peek();
}

public int min(){
	if(size==0) return 0;
	return minPq.peek();
}

 

 

Solution()에서 연산을 처리

 

이제는 Solution() 내부에서 연산을 처리해주기 위한 작업을 해주면 된다. 명령어는 3가지로 나뉜다.

 

• | 숫자 : 큐에 주어진 숫자를 삽입
• D 1 : 큐에서 최댓값 삭제
• D -1 : 큐에서 최솟값 삭제

 

operations를 “ “ 를 기준으로 커맨드와 숫자를 분리한 뒤, 커맨드가 | 일 경우, 숫자를 삽입하고

커맨드가 D일 경우에는 숫자가 1이면 최댓값을 삭제하고 숫자가 -1이면 최솟값을 삭제하도록 구현하자.

value는 String이기 때문에 add()를 할때 Integer.parseInt()로 숫자형으로 변경한 뒤 넘겨주어야 한다.

 

DoublyPriorityQueue dpq = new DoublyPriorityQueue();

for(String operation : operations){
	String[] tokens = operation.split(" ");
	String command = tokens[0];
	Stirng vlaue = tokens[1];

	switch(command){
		case "I" -> dpq.add(Integer.parseInt(value));
		case "D" -> {
			if(value.equals("1")) dpq.removeMax(value);
			else dqp.removeMin(value);
		}
	}
}

 

 

max/min 값 리턴

 

마지막으로 max값과 min값을 찾은 뒤 리턴해주면 끝이다!

 

return new int[]{dpq.max(), dpq.min()};

 

---

전체 코드

 

import java.util.PriorityQueue;

public class Solution{
    private static class DoublyPriorityQueue{
		private int size =0;
		private PriorityQueue<Integer> minPq = new PriorityQueue<>();
		private PriorityQueue<Integer> maxPq = new PriorityQueue<>( (a,b)-> b-a);

		private void add(int value){
			minPq.add(value);
			maxPq.add(value);
			size++;
		}

		private void removeMin(){
			if(size==0) return;
			minPq.poll();
			if(--size==0){
				minPq.clear();
				maxPq.clear();
			}
		}

		private void removeMax(){
			if(size==0) return;
			maxPq.poll();
			if(--size==0){
				minPq.clear();
				maxPq.clear();
			}
		}
		
		private int max(){
			if(size==0) return 0;
			return maxPq.peek();
		}

		private int min(){
			if(size==0) return 0;
			return minPq.peek();
		}
	}
	
	public int[] solution(String[] operations){
		DoublyPriorityQueue dpq = new DoublyPriorityQueue();
		
		for(String operation : operations){
			String[] tokens = operation.split(" ");
			String command = tokens[0];
			String value = tokens[1];
			
			switch(command){
				case "I" -> dpq.add(Integer.parseInt(value));
				case "D" -> {
					if(value.equals("1")) dpq.removeMax();
					else dpq.removeMin();
				}
			}
		}
		return new int[]{dpq.max(), dpq.min()};
	}
}

 

---

 

참고

• 프로그래머스 이중순위큐
• 취업과 이직을 위한 프로그래머스 코딩 테스트 문제 풀이 전략: 자바 편