우선순위 큐를 사용할 수 있는지 묻는 문제이다. 우선순위 큐란 기본적으로 큐의 성질을 가지고 있으면서 내부에 특정 우선순위를 부여할 경우 우선순위에 맞게 값이 나오는 것을 말한다.
Heap 구조로 구현되어 있기 때문에 주요 메서드인 put(), get()은 의 시간복잡도를 가진다.
Python
자료구조를 설명하는 시간은 아니니 생략하도록 하고, 파이썬에서 우선순위 큐를 사용하는 방법은 다음과 같다.
queue에서 우선순위 큐 클래스 가져오기
from queue import PriorityQueue비어있는 우선순위 큐 선언
myPriorityQueue = PriorityQueue()우선순위 큐에 데이터 삽입
put() 메서드를 통해 데이터를 삽입한다. default로 오름차순으로 정렬하여 데이터를 삽입하며, 데이터 크기만 넣을 경우 넣는 순서에 따라 자동으로 번호가 1부터 부여된다.
만약 별도로 지정한 기준을 설정할 경우 (우선순위, 데이터)과 같이 tuple 형태로 데이터를 넣을 수 있다.
이 경우 별도로 지정한 우선순위를 따르며, 만약 우선순위의 값이 동일할 경우 데이터크기를 비교하여 오름차순으로 정렬되어 값이 들어간다.
// 데이터만 넣을 경우
myPriorityQueue.put(data)
// 별도로 지정한 기준을 설정할 경우
myPriorityQueue.put((priority, data)) 우선순위 큐에 데이터 가져오기
get() 메서드를 통해 데이터를 가져온다. (우선순위, 데이터)와 같이 tuple를 통째로 반환하므로 데이터 값만 알고 싶다면 인덱스 연산을 통해 가져와야 한다.
temp = myPriorityQueue.get()
print(temp[1]) // 데이터 출력문제에서는 절댓값이 가장 작은 값을 출력하면서, 동일한 값이 여러개일 경우 가장 작은 수를 출력하라고 요구하였다.
절댓값을 기준으로 우선순위만 정해주면 가장 작은 수 출력은 default로 오름차순 정렬되는 것과 같으므로 별도로 조치할 필요가 없다.
따라서 문제풀이 방법은 다음과 같다.
-
요청한 값이 0인 경우:
큐가 비어있으면 0 출력, 비어 있지 않으면 큐의 front값 출력(get 메서드 사용) -
요창한 값이 0이 아닌 경우:
새로운 데이터를 절댓값 기준으로 우선순위를 설정하여 큐에 삽입(put 메서드 사용)
from queue import PriorityQueue
import sys
# 표준 출력으로 설정
print = sys.stdout.write
# 표준 입력으로 설정
input = sys.stdin.readline
N = int(input())
q = PriorityQueue()
for i in range(N):
request = int(input())
# 비교연산 요청인 경우
if request == 0:
# 큐가 비어있는 경우
if q.empty():
print('0\n') # 0을 출력
# 큐가 비어있지 않은 경우
else:
# front 값 가져와서 출력
temp = q.get()
print(str(temp[1]) + '\n')
# 비교연산이 아닌 경우
else:
# 입력값의 절댓값을 기준으로 우선순위를 설정
q.put((abs(request), request))Java
자바에서 우선순위 큐를 사용하는 방법은 다음과 같다.
// 우선순위 큐 가져오기
import java.util.PriorityQueue;
// 비어있는 큐 선언
PriorityQueue<객체 타입> 변수명 = new PriorityQueue<>();우선순위를 별도로 지정하기 위해서는 Comparator 라는 인터페이스에 compare이라는 메서드를 오버라이딩 해야하며, 이를 아래와 같이 람다식을 통해 간결하게 재정의가 가능하다.
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
int first_abs = Math.abs(o1);
int second_abs = Math.abs(o2);
if (first_abs == second_abs)
return o1 > o2 ? 1 : -1;
else
return first_abs - second_abs;
});비교하는 메서드를 오버라이딩했는데 어떻게 정렬이 되는거지??라고 의문이 생길 수 있다. 이에 대한 원리는 아래 포스팅을 참고하길 바란다.
[프로그래머스] 코딩테스트에 필요한 자바 문법: Comparator, Comparable과 정렬의 관계
https://velog.io/@wonotter/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8%EC%97%90-%ED%95%84%EC%9A%94%ED%95%9C-%EC%9E%90%EB%B0%94-%EB%AC%B8%EB%B2%95#comparable-comparator%EA%B3%BC-%EC%A0%95%EB%A0%AC%EC%9D%98-%EA%B4%80%EA%B3%84
원리에 대한 상세한 설명은 제외하고 간단하게 말하면, 아래 사진과 같이 PriorityQueue를 뜯어보면 매개변수로 Comparator<? super E> 를 가지고 있어 커스텀으로 정렬 기준을 받을 수 있다.
따라서 문제풀이 방법은 다음과 같다.
-
요청한 값이 0인 경우:
큐가 비어있으면 0 출력, 비어 있지 않으면 큐의 front값 출력(poll 메서드 사용) -
요창한 값이 0이 아닌 경우:
새로운 데이터를 절댓값 기준으로 우선순위를 설정하여 큐에 삽입(add 메서드 사용)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
public class P_11286 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
PriorityQueue<Integer> queue = new PriorityQueue<>((o1, o2) -> {
int first_abs = Math.abs(o1);
int second_abs = Math.abs(o2);
if (first_abs == second_abs)
return o1 > o2 ? 1 : -1;
else
return first_abs - second_abs;
});
for (int i = 0; i < N; i++) {
int request = Integer.parseInt(br.readLine());
if (request == 0) {
if (queue.isEmpty())
System.out.println("0");
else
System.out.println(queue.poll());
} else {
queue.add(request);
}
}
}
}