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

[프로그래머스] 이중우선순위큐 : https://school.programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

---

문제 조건 정리

---

입력 / 출력

---

문제를 풀기 전

 

1. deque(덱) 구조보다 최소힙, 최대힙으로 우선순위큐(pq)를 2개 구현해야겠다. 
2. 한 개의 pq에서 삭제(dequeue)가 일어나면, 나머지 pq에서도 삭제가 일어나야 하는데 어떻게 구현하지?
   1. 나머지 pq에서 remove 연산 -> remove 를 위한 힙 탐색 -> 탐색 트리가 아니므로 O(logN) 이 아닌 O(N) 만큼 걸릴 듯
   2. 배열이나 리스트에 삭제된 데이터들을 저장? -> 이것도 O(N)
   3. 배열이나 리스트에 입력된 데이터들 중에서 명령에 따라 삭제되고 남은 데이터? -> 이것도 O(N)
   4. 해시맵에 입력 데이터를 key로 정하고, key의 입력마다 value 증가, 삭제되면 value를 감소시키는 형태 -> O(1)
3. 해시맵에 대한 예외를 깔끔히 처리해주며 입력과 삭제를 관리해야겠다.
   

 

---

코드

 

package programmers;

import java.util.*;

public class 이중우선순위큐 {

    static class Solution {

        public static void main(String[] args) {
            solution(new String[]{"I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"});
        }

        static public int[] solution(String[] operations) {
            int[] answer = {};

            // 최소힙
            PriorityQueue<Integer> minPQ = new PriorityQueue<>();
            // 최대힙
            PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());
            // 해시맵 <데이터 값, 데이터 개수>
            HashMap<Integer, Integer> inputHMap = new HashMap<>();

            // 각 입력 연산을 처리
            for (String operation : operations) {

                // I, D 를 구분
                char command = operation.charAt(0);
                int data = 0;

                // data 의 부호 처리
                char sign = '+';
                char signCheck = operation.charAt(2);
                if (signCheck == '-') {
                    sign = '-';
                } else {
                    // '-' 기호가 없다면 바로 숫자이므로 예외 처리
                    // char 값에 '0' 을 빼면 올바른 int 값을 얻을 수 있음.
                    data = signCheck - '0';
                    //Character.getNumericValue()
                }

                // 남은 데이터를 읽음
                for (int i = 3; i < operation.length(); i++) {
                    data *= 10;
                    data += operation.charAt(i) - '0';
                    //Character.getNumericValue()
                }

                // 부호 처리
                if (sign == '-') {
                    data *= -1;
                }

                // 입력일 경우
                if (command == 'I') {
                    // 각 pq 에 넣어주고, 해시맵에도 넣어줌
                    minPQ.offer(data);
                    maxPQ.offer(data);
                    inputHMap.put(data, inputHMap.getOrDefault(data, 0) + 1);
                }
                // 삭제일 경우 (else)
                else if (command == 'D') {
                    if (data == 1) {
                        // 최대값 삭제
                        removeInHM(maxPQ, inputHMap);
                    } else if (data == -1) {
                        // 최소값 삭제
                        removeInHM(minPQ, inputHMap);
                    }
                }
            }

            int min = checkValidValue(minPQ, inputHMap);
            int max = checkValidValue(maxPQ, inputHMap);

            for (Map.Entry<Integer, Integer> entry : inputHMap.entrySet()) {
                System.out.println(entry);
            }

            System.out.println(max);
            System.out.println(min);

            answer = new int[]{max, min};

            return answer;
        }

        private static int checkValidValue(PriorityQueue<Integer> pq, HashMap<Integer, Integer> inputHMap) {
            while (!pq.isEmpty()) {
                // 해당 pq의 루트 노드를 체크
                int peek = pq.peek();

                // 그 값의 개수가 0개 초과인지 해시맵에서 체크
                if (inputHMap.get(peek) > 0) {
                    return peek;
                }
                // 0개 이하라면 dequeue, 다시 위 과정 진행
                pq.poll();
            }

            // 해당 pq가 비었다면 -> 유효한 값이 하나도 없다 -> 0 반환
            return 0;
        }

        private static void removeInHM(PriorityQueue<Integer> pq, HashMap<Integer, Integer> inputHMap) {
            while (!pq.isEmpty()) {
                // 해당 pq 를 dequeue
                int poll = pq.poll();

                // dequeue 값이 해시맵에서 확인했을 떄, 1개 이상이라면 1을 뺀다.
                // 1개 이상이라는 것은 유효한 데이터라는 것, 1개 이상이 아니였다면 이는 이미 삭제된 값이므로 반복해야함.
                // 0개 일때는 빼면 안됨! -> 무시해야하는 연산이므로..
                if (inputHMap.get(poll) > 0) {
                    inputHMap.put(poll, inputHMap.get(poll) - 1);
                    break;
                }
            }
        }
    }
}

 

---

문제를 풀고 난 후

 

다른 알고리즘의 풀이보다 ~20배 가량 빠른 시간으로 문제를 해결할 수 있었다.

해시맵 최고