알고리즘 - 힙(이중우선순위큐)

• 문제 출처 : 프로그래머스
• 문제명 : 이중우선순위큐
• 분류 : 큐
• 언어 : Java (Open jdk 1.8)
• 체감 난이도 : ⭐⭐⭐⭐⭐
• Fail Cnt : 5
• Fail 이유 : 프로세스 오류
• 최대힙과 최소힙 사용을 익힐 수 있으며 hashMap 사용법 또한 익힐 수 있는 좋은 문제

알고리즘 설계

변수

1) hashMap : 최대힙, 최소힙을 구분했기 때문에 사용했다. key는 큐에 삽입한 숫자이고 value는 큐에 남아있는 해당 숫자의 개수이다.
2) minHeap : 자바 내장 우선순위 큐 타입인 PriorityQueue를 사용했다.
3) maxHeap : 자바 내장 우선순위 큐 타입인 PriorityQueue는 minHeap이므로, Comparator/compare를 사용해 maxHeap으로 만들어 사용했다.

        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

프로세스 설계

1) solution메소드의 파라미터로 주어지는 명령을 순차적으로 수행한다.

1) 삽입 명령인 경우

1) 삽입할 숫자가 음수인지 양수인지에 따라 Integer형으로 변환
2) hashMap에 숫자 카운팅 해서 저장
3) minHeap과 maxHeap에 add

2) 삭제 명령인 경우

1) 최솟값 삭제인지 최댓값 삭제인지 구분해서, poll()한 숫자의 hashMap value가 0이 아닐때 까지 반복
2) poll()한 숫자의 hashMap value가 0이면 해당 숫자의 개수를 -1해주고 break

2) 최댓값, 최솟값으로 answer배열 저장

Fail Code

계속 5번 TC가 fail

    public int[] solution(String[] operations) {
        int[] answer = {};
        String numStr = ""; //문자열 부분 중 숫자 알아낵
        int strToNum = 0;   int findNum = 0;
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });

        for(int i=0; i<operations.length; i++) {
            if(operations[i].charAt(0) == 'I') {    //삽입
                if(operations[i].charAt(2) == '-') {    //음수
                    numStr = operations[i].substring(3, operations[i].length());
                    strToNum = Integer.valueOf(numStr);
                    strToNum *= -1;
                } else {    // 양수
                    numStr = operations[i].substring(2, operations[i].length());
                    strToNum = Integer.valueOf(numStr);
                }
                //HashMap에 저장
                if(hashMap.containsKey(strToNum)) { //이미 있는 숫자면
                    hashMap.put(strToNum, new Integer(hashMap.get(strToNum) + 1));  //카운팅 +1
                } else {    //해당 숫자 첫번째이면
                    hashMap.put(strToNum, new Integer(1));
                }
                //힙에 넣기
                minHeap.add(strToNum);
                maxHeap.add(strToNum);
            } else {    //삭제
                if(operations[i].charAt(2) == '-') {    //최솟값 삭제
                    while(minHeap.size() > 0) { //minHeap 안 비어 있으면
                        findNum = minHeap.poll();   //해당 숫자 있는지 확인
                        if(hashMap.get(findNum) > 0) {
                            hashMap.put(findNum, new Integer(hashMap.get(findNum) - 1));   //개수 -1
                            break;
                        }
                    }
                } else {    //최댓값 삭제
                    while(maxHeap.size() > 0) {
                        findNum = maxHeap.poll();
                        if(hashMap.get(findNum) > 0) {
                            hashMap.put(findNum, new Integer(hashMap.get(findNum) - 1));
                            break;
                        }
                    }
                }
            }
        }


        answer = new int[2];
        //일단 없는거로 초기화
        answer[0] = answer[1] = 0;
        while(!maxHeap.isEmpty()) {
            findNum = maxHeap.poll();
            if (hashMap.get(findNum) > 0) {  //최댓값있으면
                answer[0] = findNum;
                break;
            }
        }
        while(!minHeap.isEmpty()) {
            findNum = minHeap.poll();
            if(hashMap.get(findNum) > 0) {
                answer[1] = findNum;
                break;
            }
        }

        if(answer[0] == 0 && answer[1] != 0) {
            answer[0] = answer[1];
        }
        if(answer[0] != 0 && answer[1] == 0) {
            answer[1] = answer[0];
        }

        return answer;
    }

문제가 되었던 코드

        if(answer[0] == 0 && answer[1] != 0) {
            answer[0] = answer[1];
        }
        if(answer[0] != 0 && answer[1] == 0) {
            answer[1] = answer[0];
        }

어쩌피 해당 코드 직전에 수행하는 while(!maxHeap.isEmpty()) / while(!minHeap.isEmpty())문에서 올바르게 최댓값, 최솟값을 찾아내는데 쓸데없는 예외 처리한다고 이상한 코드를 작성함.

해당 코드를 지운 후, 테스트 통과함