전공공부
[BOJ_7662] 이중 우선순위 큐 본문
설명
맞왜틀을 계속 시도했었던 문제 TestCase 새로 시작되면서 map을 당연히 초기화 해야하는데 그 생각을 못하고 계속 12%에서 틀렸었다.
어쨌든 Red Black Tree를 사용하는 TreeMap API를 활용하여서 OlogN으로 찾을 수 있었다. 또한, 최대 값과 최솟 값을 가져오기 정상적으로 가져오기 위해서 같은 수가 두 번 이상 들어올 때와 아예 사라질때 remove가 될때를 주의해서 구현하였다.
코드
package Data_Structure;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class BOJ_7662 {
public static void main(String[] args) throws Exception{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tk = new StringTokenizer(in.readLine(), " ");
int T = Integer.parseInt(tk.nextToken());
TreeMap<Integer,Integer> map;
while(T-- > 0){
map = new TreeMap<>();
tk = new StringTokenizer(in.readLine(), " ");
int N = Integer.parseInt(tk.nextToken());
while(N-- > 0){
tk = new StringTokenizer(in.readLine(), " ");
String str = tk.nextToken();
int n = Integer.parseInt(tk.nextToken());
if(str.equals("I")){
map.put(n, map.getOrDefault(n, 0) + 1);
}else if (str.equals("D") && !map.isEmpty()){
if(n == -1) {
int minKey = map.firstKey();
if (map.get(minKey) == 1)
{
map.remove(minKey);
}else{
map.put(minKey,map.get(minKey)-1);
}
}else {
int maxKey = map.lastKey();
if (map.get(maxKey) == 1)
{
map.remove(maxKey);
}else{
map.put(maxKey,map.get(maxKey)-1);
}
}
}
}
if (map.isEmpty()) {
System.out.println("EMPTY");
} else {
System.out.println(map.lastKey() + " " + map.firstKey());
}
}
}
}
https://www.acmicpc.net/problem/7662
7662번: 이중 우선순위 큐
입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적
www.acmicpc.net
'Study > Problem Solving' 카테고리의 다른 글
[BOJ_21921] 블로그 (0) | 2023.11.08 |
---|---|
[BOJ_11728] 배열 합치기 (0) | 2023.11.07 |
[BOJ_2075] N번째로 큰 수 (0) | 2023.11.05 |
[BOJ_22942] 데이터 체커 (1) | 2023.11.04 |
[BOJ_19532] 수학은 비대면강의입니다. (1) | 2023.11.03 |