안녕하세요 이번 시간에는 우선 순위 큐 문제 유형을 확인하며 어떻게 적용시켜야 하는지에 대해 포스팅해보도록 하겠습니다.
우선 첫 번째 유형은 정렬을 사용해야 하지만 배열이나 리스트를 사용하면 안되는 문제입니다. 주로 배열이나 리스트를 정렬했을 경우 시간 초과가 발생하고 중간 인덱스를 탐색할 필요가 없는 문제들입니다. 이 문제들을 우선 순위 큐의 정렬 특성을 이용하여 배열이나 리스트를 정렬 시 소요되는 시간을 감소시킬 수 있습니다. 또한 자바의 경우 우선 순위 큐 또는 큐에 넣을 클래스에 Comparable<T> 또는 Comparator<T> 인터페이스를 오버라이딩하여 원하는 정렬 조건을 커스텀할 수 있습니다.
Comparable<T>와 Comparator<T>는 둘 다 객체의 정렬에 사용되는 인터페이스이지만 약간의 차이가 존재합니다. Comparable<T>의 경우 public int compareTo(T o) 메서드를 구현하여 자신과 다른 객체들에 대한 비교를 진행합니다. 하지만 Comparator<T>의 경우 public int compare(T o1, T o2) 메서드를 이용하여 파라미터로 받은 두 객체를 비교하여 결과를 반환합니다. 쉽게 말해 클래스가 피연산자처럼 동작하는 클래스의 경우 Comparable<T>를 구현하여 다른 자료구조에서 정렬 시 기준대로 정렬되도록 하고, 클래스가 연산자처럼 동작하는 클래스의 경우 Comparator<T>를 구현하여 다른 자료구조를 기준에 맞게 정렬할 때 사용하면 좋습니다.
백준 11286(절댓값 힙) 문제는 배열에 정수를 넣고 입력이 오면 절댓값이 가장 작은 값, 절댓값이 같다면 가장 작은 값을 출력하는 문제입니다. 우선 순위 큐에 Comparator<T>를 추가하여 조건에 맞게 정렬하거나 우선 순위 큐에 저장되는 클래스를 Comparable<T>를 오버라이딩하여 조건을 추가하여 진행하면 됩니다.
백준 2075(N번째 큰 수) 문제는 표 내에서 N번째 큰 수를 찾는 문제입니다. 표의 값들을 우선 순위 큐에 저장한 후 큐의 사이즈가 N보다 크다면 poll하는 방식으로 구현합니다.
백준 1715(카드 정렬하기) 문제는 카드 묶음의 최소 비교 횟수를 구하는 문제입니다. 그리디 방식으로 오름차순으로 정렬된 우선 순위 큐에 데이터를 추가한 후 두 개를 뽑아 그 합을 다시 우선 순위 큐에 저장하여 큐의 사이즈가 1이 될때까지 진행합니다.
두 번째 유형은 중간값을 구하는 문제입니다. 중간값의 특성상 수열이 정렬이 되어있어야 하고 항상 가운데를 가리키기 때문에 중간값 기준 작은 수를 담는 우선 순위 큐와 큰 수를 담는 우선 순위 큐 2개를 만들어 작은 큐는 내림차순, 큰 큐를 오름차순 정렬을 합니다. 이렇게 되면 저번 포스팅의 스택의 "커서를 활용하는 문제"처럼 현재 값 기준으로 좌우에 정렬된 값들을 얻을 수 있어 중간값을 구할 수 있습니다. 여기서 주의할 점은 두 큐의 차이가 1 이하로 계속 유지되어야 한다는 점입니다. 두 값이 1보다 크게 된다면 중간값이 아니라 이상한 부분을 참조하게 되어 오류가 발생합니다.
백준 1655(가운데를 말해요) 문제와 2696(중앙값 구하기)가 대표적인 문제입니다. 주어진 입력을 중간값 기준 작은 수와 큰 수를 담는 우선 순위 큐에 각각 저장하고 기준으로 한 큐를 1 더 크게 하여 데이터를 추가합니다. 이 때 중간값 구하는 로직을 수행한 후 기준으로 한 큐의 피크값을 출력하면 됩니다.
