[프로그래머스] 이중 우선순위 큐 Java

1. 문제 설명

문제 링크

2. 접근 방식

TreeMap을 이용해서 접근했다.
TreeMap은 Key 값을 기준으로 정렬된 자료구조를 말한다. 정렬 기준은 default가 오름 차순이고, 매개변수로 Comparator를 넣어서 바꿀 수 있다. 이때 주의할 것은 대소관계 비교는 "Key" 값으로 이루어진다는 것이다.

TreeMap<Student,String> map = new TreeMap<>((o1,o2) -> (return Integer.compare(o1.score, o2.score)));

여기서 주의해야할 점은

1. 값에 중복이 있다.
2. 최대값, 최소값 중 어느 것도 빠져나갈 수 있다.

이다.
다행히 TreeMap은 deque처럼 rear부분과 front 부분을 둘 다 조회 가능하다. (삭제도 바로바로 될 것 같은데, 이 부분은 자료 구조를 더 찾아봐야겠다.)
map.firstKey() -> 오름 차순 정렬 시, 가장 작은 값,
map.lastKey() -> 오름 차순 정렬 시, 가장 큰 값
임을 유의해서, 각 명령어에 맞게 삭제한다. 다만 중복되는 값이 들어오면 해당 값을 key로 가지는 value를 1올린다. 만약 93이 2번 들어오면 <key,value> = <93,2> 가 된다. 삭제할 때도 value를 다 깎고, 만약에 value가 0이 되면 해당 entry를 map에서 지우면 된다.

3. 코드 분석

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

class Solution {
    public int[] solution(String[] operations) {

        TreeMap<Integer,Integer> map = new TreeMap<>();

        for(int i = 0; i < operations.length; i++){
            StringTokenizer st = new StringTokenizer(operations[i]);
            String order = st.nextToken();

            switch(order){
                case "I": {
                    int v = Integer.parseInt(st.nextToken());
                    if(map.get(v) == null){
                        map.put(v, 1);
                    }else {
                        map.put(v, map.get(v)+1);
                    }
                    break;
                }
                case "D": {

                    if(map.isEmpty()) break;

                    int order2 = Integer.parseInt(st.nextToken());
                    int k = 0;
                    if(order2 == 1) {
                        k = map.lastKey();
                    }else {
                        k = map.firstKey();
                    }
                    if(map.get(k) >= 2) {
                        map.put(k, map.get(k)-1);
                    }else if(map.get(k) == 1){
                        map.remove(k);
                    }
                    break;
                }
            }
        }



        if(map.size() == 0) return new int[]{0,0};
        else {
            return new int[]{map.lastKey(), map.firstKey()};
        }

    }
}

4. 성장 하기

TreeMap을 쓰지 않은 사람들의 풀이가 흥미로웠다.
다른 풀이로는 우선순위큐를 2개 만들고, HashMap을 사용한다. map은 해당 값이 실제로 존재하는지에 대한 명부라고 보시면 된다.

1. 오름 차순 정렬된 우선순위 큐(A)와 내림차순 정렬된 우선순위 큐(B)를 둔다.
2. 값 삽입 시에는 두 큐에 전부 삽입 및, map에도 값을 적어놓는다.
3. 최소값 삭제 시, A에서 값을 삭제한다. 다만 이때, 삭제하려고 봤던 A.poll()한 수가 명부에 없는 값이라면, 이미 다른 명령어에 의해 삭제된 숫자 임으로, 다시 삭제한다는 것이 무의미 하다. 따라서 명부에 존재하는 값이 나올 때까지 queue에서 poll() 한다. (최대값도 마찬가지)
4. 명령어 계산이 끝난 후에는 KeySet()을 뽑아서, 최대값과 최소값을 출력한다.

느낀 점 : map의 매소드들과 더 익숙해져야겠다. treeMap의 매소드도 알아둬야겠다는 생각이 든다.
그리고 처음에는 우선순위 Queue의 remove()라는 함수를 쓰려고 했는데 해당 함수는 모든 값을 선형적으로 돌아서 사용자가 원하는 값을 찾아낸 뒤 삭제하는 것이라 O(n)의 시간복잡도가 든다. 이 때문에 시간초과가 많이 났었다. queue의 remove()는 선형적인 조회를 해서 삭제 속도가 느리다는 것을 알고 가자.

5. 다른 풀이

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;
        TreeMap<Integer, Integer> map = new TreeMap();
        int T = Integer.parseInt(br.readLine());

        for (int t=0; t<T; t++) {
            int k = Integer.parseInt(br.readLine());
            char command;
            int num;
            int targetNum;
            for (int i=0; i<k; i++) {
                st = new StringTokenizer(br.readLine());
                command = st.nextToken().charAt(0);
                num = Integer.parseInt(st.nextToken());

                if (command == 'I') {
                    map.put(num, map.getOrDefault(num, 0) + 1);
                } else if (!map.isEmpty()) {
                    if (num == -1) {
                        targetNum = map.firstKey();
                        if (map.get(targetNum) == 1) {
                            map.remove(targetNum);
                        } else {
                            map.put(targetNum, map.get(targetNum) - 1);
                        }
                    } else {
                        targetNum = map.lastKey();
                        if (map.get(targetNum) == 1) {
                            map.remove(targetNum);
                        } else {
                            map.put(targetNum, map.get(targetNum) - 1);
                        }
                    }
                }
            }
            if (map.isEmpty()) {
                sb.append("EMPTY");
            } else {
                sb.append(map.lastKey()).append(' ').append(map.firstKey());
            }
            sb.append('\n');
            map.clear();
        }
        System.out.println(sb);
    }
}