[BOJ] 7662번 이중 우선순위 큐 Java 오답노트

이중 우선순위 큐

오답 1 - 틀렸습니다

• 문제에서 각 값의 중복을 허용(같은 값이 있을 시 구분하여 삭제)하고 있다는 점을 발견하지 못하고 HashSet을 사용하여 이중 우선순위 큐를 구현하여 틀렸다.
• 다음으로 넘어가 중복을 구분할 수 있는 다른 풀이로 도전.
• HashSet 참고: https://coding-factory.tistory.com/554
• Double Ended Priority Queue 참고: https://www.geeksforgeeks.org/double-ended-priority-queue/

import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    // HashSet을 사용하여 이중 우선순위 큐를 구현한다.
    static class DualPriorityQueue{
        Set<Integer> s;
        DualPriorityQueue(){
            s = new HashSet<Integer>();
        }

        int size(){
            return s.size();
        }

        boolean isEmpty(){
            return (s.size()==0);
        }

        void insert(int x){
            s.add(x);
        }

        int getMax(){
            return Collections.max(s,null);
        }

        void deleteMax(){
            if (s.size() == 0) return;
            s.remove(Collections.max(s,null));
        }

        int getMin(){
            return Collections.min(s,null);
        }

        void deleteMin(){
            if (s.size() == 0) return;
            s.remove(Collections.min(s,null));
        }


    }
    public static void main(String[]args){
        /*[문제]
        이중 우선순위 큐
        우선순위 큐와의 공통점 삽입, 삭제할 수 있는 자료 구조인 점
        전형적인 큐와의 차이점 삭제할 때 연산 명령에 따라 우선순위가 가장 높은 데이터 또는 가장 낮은 데이터 중 하나를 삭제하는 점

        이중 우선순위 큐의 두 가지 연산
        데이터를 삽입
        (우선순위가 가장 낮은 것/우선순위가 가장 높은 것) 데이터를 삭제

        정수만 저장하는 이중 우선순위 큐
        저장된 각 정수의 값 자체를 우선순위로 간주
        큐에 적용될 일련의 연산이 주어질 때 이를 처리한 후 최종적으로 큐에 저장된 데이터 중 최댓값과 최솟값을 출력 */

        // 표준입력을 사용한다.
        // T개의 테스트 데이터를 입력받는다.
        Scanner scan = new Scanner(System.in);
        int t = scan.nextInt();
        for(int i=0; i<t; i++){
            // 이중 우선순위 큐를 선언한다.
            DualPriorityQueue dpq = new DualPriorityQueue();

            // Q에 적용할 연산의 개수를 나타내는 정수 k를 입력받는다.
            int k = scan.nextInt();
            for(int j=0;j<k;j++){
                // 연산을 나타내는 문자와 정수 n을 입력받는다.
                String str = scan.next();
                int n = scan.nextInt();
                // I n인 경우 n을 dpq에 삽입
                if (str.equals("I")) dpq.insert(n);
                // D 1인 경우 최댓값을 삭제
                else if (str.equals("D") && n==1) dpq.deleteMax();
                // D -1인 경우 최솟값을 삭제
                else if (str.equals("D") && n==-1) dpq.deleteMin();
            }

            if (dpq.isEmpty()) System.out.printf("EMPTY");
            else {
                System.out.printf(dpq.getMax()+" "+dpq.getMin());
            }
        }
    }
}

오답 2 - 시간 초과

• 우선순위 큐는 힙을 이용하여 구현하는 것이 일반적이기 때문에 최대, 최소를 알고 싶기 때문에 최소힙, 최대힙을 사용하여 구현해보았다.
• 하지만, getMin, getMax구현부에서 remove을 사용해 특정 값을 지우게 되는데 여기서 시간 복잡도가 O(n)으로 시간초과가 발생하게 된다. 왜냐하면 내부적으로 contains() 사용하게 되는데 탐색에서 O(n)이 되게된다.
• Priority Queue 참고: https://coding-factory.tistory.com/603
• Priority Queue remove time complexity 참고: https://stackoverflow.com/questions/12719066/priority-queue-remove-complexity-time

import java.util.*;

public class Main {

    /*
        풀이 설계
        1. 삽입, 삭제 연산
        2. 우선순위에 다른 최대, 최소 값 탐색 필요
        3. 입력된 요청에 따라 삽입, 최대 삭제, 최소 삭제 -> 로직
        4. 정수를 저장하며 값 자체가 우선순위

        입력
        1. T개의 테스트
        2. K개의 연산 -> 100만 개의 값
            문자 명령어와 정수 값

        출력
        1. 최종적으로 자료구조에 저장된 최대, 최소 출력.
            비어있는 경우 "EMPTY"
    */

    static class DualPriorityQueue{

        PriorityQueue<Integer> minHeap;
        PriorityQueue<Integer> maxHeap;

        DualPriorityQueue(){
            minHeap = new PriorityQueue<Integer>();
            maxHeap = new PriorityQueue<Integer>(Collections.reverseOrder());
        }

        int size(){
            return minHeap.size()+ maxHeap.size();
        }

        boolean isEmpty(){
            return (size() == 0);
        }

        void insert(int n){
            minHeap.offer(n);
            maxHeap.offer(n);
        }

        int getMax(){
            if (maxHeap.size() == 0) return 0;
            int max = maxHeap.poll();
            minHeap.remove(max);
            return max;
        }

        int getMin(){
            if (minHeap.size() == 0) return 0;
            int min = minHeap.poll();
            maxHeap.remove(min);
            return min;
        }
    }

    public static void main(String[]args){
        Scanner scan = new Scanner(System.in);

        int T = scan.nextInt();
        for(int i=0; i<T; i++){

            DualPriorityQueue dpq = new DualPriorityQueue();

            int K = scan.nextInt();

            for(int j=0;j<K;j++){
                String str = scan.next();
                int n = scan.nextInt();

                if (str.equals("I")) dpq.insert(n);
                else if (str.equals("D") && n==1) dpq.getMax();
                else if (str.equals("D") && n==-1) dpq.getMin();
            }

            if (dpq.isEmpty()) System.out.println("EMPTY");
            else {
                System.out.println(dpq.getMax()+" "+dpq.getMin());
            }
        }
    }
}

해결 코드 - 맞았습니다!!

• TreeMap은 키와 값이 저장된 Map으로 Key와 개수를 저장하여 구현하였다.
• 또한, TreeMap은 저장 동시에 오름차순으로 정렬하여 최대값, 최소값을 바로 알 수 있다.
• TreeMap은 이진탐색트리의 문제점을 보완한 Red-Black Tree로 이루어져 있어 편향된 값 탐색도 문제가 없다.
• 풀이 참고: https://codeung.tistory.com/315
• TreeMap 참고:https://coding-factory.tistory.com/557
• TreeMap getOrDefault(key,defaultValue) method 참고: https://www.geeksforgeeks.org/hashmap-getordefaultkey-defaultvalue-method-in-java-with-examples/

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    /*
        풀이 설계
        1. 삽입, 삭제 연산
        2. 우선순위에 다른 최대, 최소 값 탐색 필요
        3. 입력된 요청에 따라 삽입, 최대 삭제, 최소 삭제 -> 로직
        4. 정수를 저장하며 값 자체가 우선순위

        입력
        1. T개의 테스트
        2. K개의 연산 -> 100만 개의 값
            문자 명령어와 정수 값

        출력
        1. 최종적으로 자료구조에 저장된 최대, 최소 출력.
            비어있는 경우 "EMPTY"
    */

    public static void main(String[]args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

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

            TreeMap<Integer,Integer> treeMap = new TreeMap<>();
            int K = Integer.parseInt(br.readLine());

            for(int j=0;j<K;j++){
                st = new StringTokenizer(br.readLine());
                String str = st.nextToken();
                int n = Integer.parseInt(st.nextToken());

                if (str.equals("I")) treeMap.put(n, treeMap.getOrDefault(n,0)+1);
                else if (str.equals("D") && n==1 && !treeMap.isEmpty()){
                    int maxKey = treeMap.lastKey();
                    if(treeMap.get(maxKey) == 1) {
                        treeMap.remove(maxKey);
                    }else {
                        treeMap.put(maxKey, treeMap.get(maxKey) - 1);
                    }
                }
                else if (str.equals("D") && n==-1 && !treeMap.isEmpty()){
                    int minKey = treeMap.firstKey();
                    if(treeMap.get(minKey) == 1) {
                        treeMap.remove(minKey);
                    }else {
                        treeMap.put(minKey, treeMap.get(minKey) - 1);
                    }
                }
            }

            if (treeMap.isEmpty()) sb.append("EMPTY\n");
            else {
                sb.append(treeMap.lastKey()+" "+treeMap.firstKey()+"\n");
            }
        }
        System.out.println(sb);
    }
}