-
TreeMap을 이용해서 구현하였다.
-
TreeMap은 이진탐색 트리의 문제점을 보완한 레드-블랙 트리로 이루어져 있음 일반적인 이진 탐색 트리는 트리의 높이만큼 시간이 필요함.
-
하지만 값이 전체 트리에 잘 분산되어 있는 트리라면 효율성에 큰 문제가 없지만, 데이터가 들어올 때 값이 한쪽으로 편향되게 들어올 경우 비효율적일 수 있음
-
레드 - 블랙 트리는 부모 노드보다 작은 값을 가지는 노드는 왼쪽 자식, 큰 값을 가지는 가지는 노드는 오른쪽 자식으로 배치하여 균형을 맞춤
-
여기서 TreeMap이란 이진트리를 기반으로한 Map 컬렉션 중 하나이다
-
같은 Tree 구조로 이루어진 TreeSet과의 차이점은 TreeSet은 그냥 값을 저장하기만 한다면, TreeMap은 키와 값이 저장된 Map, Entry를 저장한다는 점
-
TreeMap에 객체를 저장하면 자동 정렬 되는데, 키는 저장과 동시에 자동 오름차순으로 정렬된다. (문자열일 경우 유니코드)
-
TreeMap은 일반적으로 Map으로써 성능이 HashMap보다 떨어지며 , TreeMap은 데이터를 저장할 때 즉시 정렬하기에 추가나 삭제가 HashMap보다 오래걸림
알고리즘
-
값을 입력. 값을 입력하기 전에 command를 구분함 I= Input 다음 Token에 존재하는 정수를 TreeMap에 삽입
-
'D 1' 은 최댓값을 삭제하는 연산 'D -1'은 최솟값을 삭제하는 연산임
-
끝에 TreeMap에서 최댓값과 최솟값을 출력 비어있다면 EMPTY 출력
package Gold_4;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class Priority_Queue_2 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(br.readLine());
//7662번
for(int test = 0; test <T; test++){
int input = Integer.parseInt(br.readLine());
TreeMap<Integer,Integer> map = new TreeMap<>();
for(int i = 0; i<input; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
String op = st.nextToken();
if(op.equals("I")){
int num = Integer.parseInt(st.nextToken());
map.put(num,map.getOrDefault(num,0)+1);
}else{
if(map.size() == 0) continue;
int type = Integer.parseInt(st.nextToken());
int num;
if(type == 1){
num = map.lastKey(); //최댓값 삭제
}else{
num = map.firstKey(); //최솟값 삭제
}
if(map.put(num,map.get(num) - 1) == 1){
map.remove(num);
}
/*삭제 연산일 경우 입력받은 num을 put 메소드를 이용해서 업데이트.
* num의 값을 1씩 감소 시키고 num의 현재 값이 1과 같다면 즉, 하나밖에 없다면 삭제연산
* put 메서드는 맵에 키-값 쌍을 삽입하거나 키가 이미 존재하는 경우 해당 키의 값을 업데이트 함*/
}
}
if(map.size() == 0){
sb.append("EMPTY\n");
}
else{
sb.append(map.lastKey()+" "+ map.firstKey()+"\n");
}
}
System.out.println(sb.toString());
}
}
-
최솟값: firstKey() 메서드를 사용하여 트리에서 가장 작은 키를 가져올 수 있음
-
최댓값: lastKey() 메서드를 사용하여 트리에서 가장 큰 키를 가져올 수 있음.
