[백준] 7662 이중 우선순위 큐 #JAVA #이진 탐색 트리

[백준] 7662 이중 우선순위 큐 #JAVA #이진 탐색 트리

---

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Map.Entry;
import java.util.StringTokenizer;
import java.util.TreeMap;

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;

		int T = Integer.parseInt(br.readLine());
		
		for (int t = 0; t < T; t++) {
			int k = Integer.parseInt(br.readLine());

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

			for (int i = 0; i < k; i++) {
				st = new StringTokenizer(br.readLine());

				String cmd = st.nextToken();
				int number = Integer.parseInt(st.nextToken());

				if (cmd.equals("I")) {
					if(tree.get(number) != null) {
						tree.put(number, tree.get(number)+1);
					}else {
						tree.put(number, 1);
					}
					
				} else if (cmd.equals("D")) {
					if (tree.isEmpty())	continue;

					if (number == 1) { // 최댓값 삭제
						Entry<Integer, Integer> entry = tree.pollLastEntry();
						if(entry.getValue() > 1) {
							tree.put(entry.getKey(), entry.getValue()-1);
						}
						
					} else if (number == -1) { // 최솟값 삭제
						Entry<Integer, Integer> entry = tree.pollFirstEntry();
						if(entry.getValue() > 1) {
							tree.put(entry.getKey(), entry.getValue()-1);
						}
					}
				}

			}
			if (tree.isEmpty()) {
				sb.append("EMPTY");
			} else {
				int max = tree.lastKey();
				int min = tree.firstKey();
				sb.append(max + " " + min);
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());

	}

}

 

 

풀이

---

문제 제목처럼 이중 우선순위 큐라는 자료구조가 있는 줄 알았다. 그런 자료구조는 자바에 존재하지 않았다.(다른 언어는 있을지도?)

그래서 일단 우선순위 큐를 이용해서 풀었다. 하나의 우선순위 큐를 두고 삭제 시 최소인 경우 poll() 메서드를 사용해서 삭제했고, 최대인 경우는 loop문을 통해 마지막 원소를 찾아 삭제 하려고 했다(loop문을 짜는 순간 시간 초과임을 알았다.)

 

시간 초과를 해결하기 위해 삭제의 시간복잡도가 O(lonN)인 트리 자료구조를 사용하여 해결하였다.

자바에서는 TreeSet 과 TreeMap 두 가지가 있다. 모두 이진 탐색 트리다.

해당 문제에서는 중복된 수가 입력이 될 수 있으므로 TreeSet을 사용하지 않고 TreeMap을 사용하였다.

 

 

주의 사항

---

• 같은 수가 입력이 될 수 있다. TreeMap을 사용하여 구현하며 중복된 입력시 <key, value>에서 value의 값이 증가하도록 구현한다.
• 삭제 시 value의 값이 1보다 큰 경우 삭제가 아니라, value 값을 -1 한다.

 

반례

---

INPUT

1 3 I 100 I 100 D 1

OUTPUT

100 100

---

잘못된 코드나 내용이 있다면 댓글을 남겨주세요. 즉시 수정하도록 하겠습니다! :)