[프로그래머스]Lv.3 이중우선순위큐

https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

---

문제

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

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

제한사항

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

입출력 예제

설계과정

1. 최소 우선순위 큐와 최대 우선순위 큐를 생성한다.

 

2. 입력받은 명령어를 토큰으로 나눠서 문자와 숫자를 구분한다.

 

3. 큐가 비어있는 상태에서 "D"가 들어오면 무시한다.

 

4.  " I " 가 들어오면 삽입, D가 들어오면 value 값에 따라 해당 값을 두 큐에서 삭제한다.

• 이 때, 최대값이든 최소값이든 삭제되는 것은 무조건 두 큐에서 다 삭제해야 한다.

5. 결과를 출력한다.

 

아래 블로그 글을 참조했다.

https://velog.io/@zayson/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Java-%EC%9D%B4%EC%A4%91-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90

[프로그래머스] 이중 우선순위 큐

---

풀이과정

1. PriorityQueue 를 통해 최소, 최대값이 우선순위인 큐를 생성한다.

• PriorityQueue : 우선순위 큐로써 FIFO 구조이며 우선순위를 결정해서 우선순위가 높은 데이터가 먼저 나가는 자료구조이다.
• 기본적으로는 최소값이 우선순위이므로 이에 해당하는 minPq를 생성한다.
• Collections.reverseOrder() 를 사용해서 우선순위를 바꾼 최대값 우선순위인 maxPq를 생성한다.

2. 입력받은 명령어를 문자와 숫자로 구분한다.

• 토큰을 이용해서 띄어쓰기 기준으로 나누면 구분할 수 있다.
• judge : 문자(D / I)
• value : 숫자

3. 큐가 비어있는 상태에서 삭제 명령어 "D"가 들어오면 무시한다.

• continue; 를 사용해서 그대로 넘긴다.
• A.equals(B) : A와 B가 동일한 값을 가지고 있으면 true를 리턴한다. 

4. 문자 "I" 명령어가 들어오면 두 큐에 value 값을 넣어준다.

• 이 때, if문 마지막에 continue; 를 넣지 않으면 다음 코드가 수행되어서 결과적으로 큐가 완전히 비고, 값이 정상적으로 출력되지 않는다.

5. 명령어 "D" 이면서 value가 0보다 작은 경우에는 두 큐에서 최소값을 제거한다.

• 최소값 큐인 minPq는 poll() 을 통해 가장 큰 우선순위인 최소값을 그대로 제거한다.
• 최대값 큐인 maxPq는 remove() 를 통해 따로 뺀 min 최소값을 큐에서 제거한다.
• 위와 마찬가지로 continue; 를 주의한다.

---

큐 관련 명령어

	동작을 수행하고 끝난다. 문제 발생 시 null 혹은 예외를 리턴한다.	동작 수행 후 값을 리턴한다. 문제 발생 시 false 를 리턴한다.
추가	add()	offer()
삭제	remove()	poll()

---

6. value가 0보다 크면 두 큐에서 최대값을 제거한다.

 

7. answer 를 리턴한다.

---

답안소스

• 프로그래머스

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
        int[] answer = {0, 0};
        
        PriorityQueue<Integer> minPq = new PriorityQueue<>();
		PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
		
		for(String x : operations) {
			StringTokenizer st = new StringTokenizer(x);
			String judge = st.nextToken();
			int value = Integer.parseInt(st.nextToken());
			
			if(minPq.isEmpty() && judge.equals("D")) {
				continue;
			}
			
			if(judge.equals("I")) {
				minPq.offer(value);
				maxPq.offer(value);
                continue;
			}
			
			if(value < 0) {
				int min = minPq.poll();
				maxPq.remove(min);
                continue;
			} else {
				int max = maxPq.poll();
				minPq.remove(max);
			}
		}
		
		if(!minPq.isEmpty()) {
			answer[0] = maxPq.poll();
			answer[1] = minPq.poll();
		}
        
        return answer;
    }
}

---

• 이클립스

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	
	public static int[] solution(String[] operations) {
		int[] answer = new int[2];
		
		PriorityQueue<Integer> minPq = new PriorityQueue<>();
		PriorityQueue<Integer> maxPq = new PriorityQueue<>(Collections.reverseOrder());
		
		for(String x : operations) {
			StringTokenizer st = new StringTokenizer(x);
			String judge = st.nextToken();
			int value = Integer.parseInt(st.nextToken());
			
			if(minPq.isEmpty() && judge.equals("D")) {
				continue;
			}
			
			if(judge.equals("I")) {
				minPq.offer(value);
				maxPq.offer(value);
				continue;
			}
			
			if(value < 0) {
				int min = minPq.poll();
				maxPq.remove(min);
				continue;
			} else {
				int max = maxPq.poll();
				minPq.remove(max);
			}
		}
		
		if(!minPq.isEmpty()) {
			answer[0] = maxPq.poll();
			answer[1] = minPq.poll();
		}
		
		System.out.print(answer[0] + "," + answer[1]);
		return answer;
	}
	
	public static void main(String[] args) {
		
//		String[] operations = new String[] {"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"};
		String[] operations = new String[] {"I -45", "I 653", "D 1", "I -642", "I 45", "I 97", "D 1", "D -1", "I 333"};
		
		solution(operations);
	}
}