[programmers] 이중우선순위큐

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

프로그래머스

 

이 문제를 풀면서 예전에 풀었던 문제가 기억이 안 나서 참고했다

https://melody-coding.tistory.com/318

[Baekjoon] 7662_이중 우선순위 큐

https://melody-coding.tistory.com/317

[자료구조] TreeMap

 

---

< 이중우선순위큐 >

 

문제 풀이 (Java)

import java.util.*;

class Solution {
	public int[] solution(String[] operations) {
		int[] answer = { 0, 0 };

		TreeMap<Integer, Integer> map = new TreeMap<>();

		for (int i = 0; i < operations.length; i++) {
			String str[] = operations[i].split(" ");
			int num = Integer.parseInt(str[1]);

			if (str[0].charAt(0) == 'I') {
				if (map.containsKey(num)) {
					map.put(num, map.get(num) + 1);
				} else {
					map.put(num, 1);
				}
			} else {
				if (map.size() == 0) {
					continue;
				}
				if (num == 1) {
					if (map.lastEntry().getValue() == 1) {
						map.remove(map.lastKey());
					} else {
						map.put(map.lastKey(), map.get(map.lastKey()) - 1);
					}
				} else {
					if (map.firstEntry().getValue() == 1) {
						map.remove(map.firstKey());
					} else {
						map.put(map.firstKey(), map.get(map.firstKey()) - 1);
					}
				}
			}
		}

		if (!map.isEmpty()) {
			answer[0] = map.lastKey();
			answer[1] = map.firstKey();
		}
		return answer;
	}
}

 

TreeMap을 선언한 후 operations를 탐색하며 다음 과정을 거친다.

 

1. I라면 map에 추가

2. D이고 map이 비었다면 다음 명령어로 넘어가기

3. D이고 1이라면 최댓값 삭제, -1이라면 최솟값 삭제

 

최종 TreeMap이 비어있지 않다면 최댓값과 최솟값을 answer에 저장한 후 반환한다.

 

---

---

 

출처: 프로그래머스 코딩 테스트 연습, 
https://school.programmers.co.kr/learn/challenges