백준 7662번 이중 우선순위 큐 JAVA

링크텍스트

설명

우선 처음에는 HashSet을 사용하여 min,max 큐를 각각 동기화해 주었는데 실패했다. 그래서 구글링을 통해 HashMap을 사용해 풀었다.

코드

import java.util.*;
import java.io.*;

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());

        while (t-- > 0) {
            PriorityQueue<Integer> min = new PriorityQueue<>();
            PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
            HashMap<Integer, Integer> count = new HashMap<>();

            int k = Integer.parseInt(br.readLine());

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

                String s = st.nextToken();
                int n = Integer.parseInt(st.nextToken());

                if (s.equals("I")) {
                    min.offer(n);
                    max.offer(n);
                    count.put(n, count.getOrDefault(n, 0) + 1);
                } else {
                    if (n == 1) {
                        while (!max.isEmpty() && count.getOrDefault(max.peek(), 0) == 0) {
                            max.poll();
                        }
                        if (!max.isEmpty()) {
                            int value = max.poll();
                            count.put(value, count.get(value) - 1);
                        }
                    } else {
                        while (!min.isEmpty() && count.getOrDefault(min.peek(), 0) == 0) {
                            min.poll();
                        }
                        if (!min.isEmpty()) {
                            int value = min.poll();
                            count.put(value, count.get(value) - 1);
                        }
                    }
                }
            }

            while (!max.isEmpty() && count.getOrDefault(max.peek(), 0) == 0) {
                max.poll();
            }
            while (!min.isEmpty() && count.getOrDefault(min.peek(), 0) == 0) {
                min.poll();
            }

            if (!max.isEmpty() && !min.isEmpty()) {
                sb.append(max.peek()).append(" ").append(min.peek()).append("\n");
            } else {
                sb.append("EMPTY\n");
            }
        }

        System.out.print(sb);
    }
}

처음에 틀린 코드

import java.util.*;
import java.io.*;

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());
	    
	    while(t-->0){
	        PriorityQueue<Integer> min = new PriorityQueue<>();
	        PriorityQueue<Integer> max = new PriorityQueue<>(Collections.reverseOrder());
            HashSet<Integer> check = new HashSet<>();

            int k = Integer.parseInt(br.readLine());

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

                String s = st.nextToken();
                int n = Integer.parseInt(st.nextToken());

                if(s.equals("I")){
                    min.offer(n);
                    max.offer(n);
                    check.add(n);
                }else{
                    if(n==1){
                        while(!max.isEmpty() && !check.contains(max.peek())){
                            max.poll(); 
                        }
                        if(!max.isEmpty()){
                        check.remove(max.poll());
                       }
                    }else{
                        while(!min.isEmpty() && !check.contains(min.peek())){
                            min.poll(); 
                        }
                        if(!min.isEmpty()){
                            check.remove(min.poll());
                        }
                    }
                        
                }
            }

            while (!max.isEmpty() && !check.contains(max.peek())) {
                max.poll();
            }
            while (!min.isEmpty() && !check.contains(min.peek())) {
                min.poll();
            }

            if(!max.isEmpty() && !min.isEmpty()){
                sb.append(max.peek()+" "+min.peek()+"\n");
            }else{
                sb.append("EMPTY\n");
            }
	    }

	    System.out.print(sb);
	}
}

참고 글

https://velog.io/@coldbottle/%EB%B0%B1%EC%A4%80Java-7662-%EC%9D%B4%EC%A4%91-%EC%9A%B0%EC%84%A0%EC%88%9C%EC%9C%84-%ED%81%90

https://kons03.tistory.com/258