이것저것 개발 블로그

https://www.acmicpc.net/problem/7662

풀이)

- 풀이1 : Priority Queue + HashMap 사용 -

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main_BJ_7662_이중우선순위큐 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int tc=0; tc<t; tc++){
            StringBuilder sb = new StringBuilder();
            int k = Integer.parseInt(br.readLine());
            PriorityQueue<Integer> minq = new PriorityQueue<>();
            PriorityQueue<Integer> maxq = new PriorityQueue<>(Collections.reverseOrder());
            HashMap<Integer, Integer> map = new HashMap<>();
            for(int i=0; i<k; i++){
                StringTokenizer st = new StringTokenizer(br.readLine());
                String command = st.nextToken();
                int num = Integer.parseInt(st.nextToken());

                if(command.equals("I")){
                    map.put(num, map.getOrDefault(num, 0) + 1);
                    minq.offer(num);
                    maxq.offer(num);
                }
                else {
                   if(map.size() != 0){
                       if(num == 1)
                           removeMap(maxq, map);
                       else
                           removeMap(minq, map);
                   }
                }
            }//k만큼

            if(map.size() == 0)
                sb.append("EMPTY\n");
            else{
                //큰 값
                int n = removeMap(maxq, map);
                sb.append(n+" ");

                //작은 값
                if(map.size() != 0){
                    int m = removeMap(minq, map);
                    sb.append(m+"\n");
                }
                else
                    sb.append(n+"\n");
            }
            System.out.print(sb);
        }//testcase
    }//main
    private static int removeMap(PriorityQueue<Integer> pq, HashMap<Integer, Integer> map){
        int num;
        while(true){
            num = pq.poll();
            int cnt = map.getOrDefault(num, 0);

            if(cnt == 0)
                continue;

            else if(cnt == 1)
                map.remove(num);

            else
                map.put(num, cnt-1);

            break;
        }//while
        return num;
    }//removeMap
}

이 방법은 문제를 보자마자 pq를 사용해야겠다는 생각을 가지고 이용했던 풀이이다.

Deque처럼 앞 뒤로 poll이 불가능하기 때문에 max, min queue를 따로 만들고 Map을 이용해 전체 원소 관리를 해준다.

1. "I"가 들어오면 min, max queue에 모두 삽입해주고, map에도 삽입하여 관리한다.

2. "D"가 들어오면 뒤의 숫자에 따라 함수(removeMap)를 실행한다

3. removeMap은 숫자에 맞는 min or max queue에서 수를 제거하고, map에서도 수 관리를 해주는 함수다.

4. queue가 비어있다면 empty를, 수가 하나라면 하나를 두 개 출력, 두 개 이상이라면 알맞게 출력해주면 끝!

- 풀이2 : TreeMap 활용 -

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

public class Main_BJ_7662_이중우선순위큐2 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for(int tc=0; tc<t; tc++) {
            int k = Integer.parseInt(br.readLine());
            TreeMap<Integer, Integer> map = new TreeMap<>();

            for(int i=0; i<k; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                String command = st.nextToken();
                int num = Integer.parseInt(st.nextToken());

                if(command.equals("I"))
                    map.put(num, map.getOrDefault(num, 0) + 1);

                else{
                    if(map.size() != 0){
                        int n;
                        if(num == 1) {
                            //TreeMap<>으로 선언해야 사용할 수 있다
                            n = map.lastKey();
                        }
                        else{
                            n = map.firstKey();
                        }

                        if(map.get(n) == 1)
                            map.remove(n);
                        else
                            map.put(n, map.get(n) - 1);
                    }//if
                }//else
            }
            if(map.size() == 0)
                System.out.println("EMPTY");
            else
                System.out.println(map.lastKey() + " " + map.firstKey());
        }//testcase
    }//main
}

HashMap만 사용해봐서 TreeMap은 처음 사용해봤다.

TreeMap은 이진트리를 기반으로 한 map이다. 또한 TreeMap에 값을 넣으면, 자동 오름차순 정렬된다!

일반적으로 HashMap보단 성능이 떨어지지만, 정렬을 유지해야하는 이 문제엔 안성맞춤이라서 treeMap이 효율성면에선 좋다.

가장 작은 수를 firstKey(), 가장 큰 수를 lastKey()를 이용해서 출력하면 된다.

위의 풀이와 논리는 같으므로 참고해보길!

참고하기 좋은 글도 공유한다!

https://girawhale.tistory.com/14