알고리즘 스터디 3주차

알고리즘 스터디 3주차 과제로 프로그래머스 ‘이중우선순위 큐’ 문제를 풀이하였다.

코딩테스트 연습 - 이중우선순위큐 | 프로그래머스 스쿨 (programmers.co.kr)

Java에서 Heap 사용하기

• Java에서는 Collection으로 Heap이 없음
• 하지만 Max-Heap과 Min-Heap을  Primary Queue를 활용하여 구현이 가능

최소 힙 사용하기

PriorityQueue<Integer> minHeap = new PriorityQueue<>();

• 이렇게 사용하여 컬렉션에 데이터를 넣으면 remove되는 peek의 값이 minHeap의 최소값이 됨
• Primary Queue는 우선순위 큐로 우선순위가 가장 낮은 값이 먼저 나오게 되는데, 우선순위가 낮다는 것은 Integer를 넣었을 때, 최소값으로 판단되므로 이렇게 구현 됨

최대 힙 사용하기

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

• PriorityQueue는 기본적으로 min heap을 구현하는데 사용되지만, Comparator를 사용하여 요소의 비교 방식을 변경해 최대 힙으로 활용할 수 있음
• compare 메서드 내에서 Integer.compare(o1, o2)를 사용하여 두 정수를 비교하고 그 결과를 반전 시켜서 최대 힙의 특성을 만들게됨
  • 내림차순으로 바꾸게됨

Priority Queue 주요 메서드

메서드 이름	내용
add(E e), offer(E e)	성공시 true 리턴, 실패시 llegalStateException. 지정된 요소를 큐에 추가
clear	큐에 저장된 모든 요소를 삭제
peek()	큐의 첫번쨰 값을 가져온다. 큐에서 삭제되지는 않음.
poll()	큐의 첫번째 값을 가져오고, 큐에서 제거
remove()	큐의 첫번째 값 제거 , 매개변수로 특정 객체를 넣어 삭제할 수도 있음
size()	큐 요소의 수를 리턴

문제 풀이 코드

• PriorityQueue 컬렉션을 활용해 최대힙과 최소힙을 각각 구현하여 데이터 삽입, 삭제를 수행

import java.util.*;

class Solution {
    public int[] solution(String[] operations) {
       //최소 힙
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        //최대 힙
        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return -Integer.compare(o1, o2);
            }
        });

        for (int i = 0; i < operations.length; i++) {
            String[] data = operations[i].split(" ");
            char operation = data[0].charAt(0);
            int number = Integer.parseInt(data[1]);

            switch (operation) {
                case 'I':
                    //데이터 삽입
                    System.out.println(number + "삽입");
                    maxHeap.add(number);
                    minHeap.add(number);
                    break;
                case 'D':
                    if (number == 1) {
                        //최댓값 삭제
                        if (maxHeap.isEmpty()) {
                            continue;
                        } else {
                            int maxNum = maxHeap.peek();
                            System.out.println(maxNum + "삭제");
                            maxHeap.remove(maxNum);
                            minHeap.remove(maxNum);
                        }
                    } else {
                        //최솟값 삭제
                        if (minHeap.isEmpty()) {
                            continue;
                        } else {
                            int minNum = minHeap.peek();
                            System.out.println(minNum + "삭제");
                            maxHeap.remove(minNum);
                            minHeap.remove(minNum);
                        }

                    }
            }
        }

        int[] answer = new int[2];

        if (!maxHeap.isEmpty() && !minHeap.isEmpty()) {
            answer[0] = maxHeap.peek();
            answer[1] = minHeap.peek();

        }
        return answer;
    }
}

(참고) https://cnu-jinseop.tistory.com/122