반응형
solved.ac에서 그리디 종류의 문제를 풀다가 우선순위 큐를 쓰게 되면서 처음 써본 거라 내용 정리 시작
우선순위 큐(Priority Queue) 사용법
우선순위 큐(Priority Queue)는 큐(Queue)와 비슷하지만, 데이터를 꺼낼 때 우선순위가 높은 순서대로 처리되는 구조이다. 자바의 PriorityQueue 클래스는 내부적으로 힙(Heap) 구조를 사용하여 구현된다.
1. 기본 생성
기본 생성자는 오름차순으로 데이터를 정렬한다.
import java.util.PriorityQueue;
public class BasicPriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(7);
queue.offer(2);
queue.offer(5);
queue.offer(1);
queue.offer(3);
System.out.println("기본 우선순위 큐:");
while (!queue.isEmpty()) {
System.out.print(queue.poll() + " ");
}
// 출력: 1 2 3 5 7
}
}2. Comparable 구현
Comparable 인터페이스를 구현하여 우선순위를 설정할 수 있다. 다음은 학생의 성적을 기준으로 우선순위를 설정하는 예제
import java.util.PriorityQueue;
class Student implements Comparable<Student> {
String name;
int score;
public Student(String name, int score) {
this.name = name;
this.score = score;
}
@Override
public int compareTo(Student other) {
return Integer.compare(this.score, other.score); // 성적 기준으로 오름차순 정렬
}
@Override
public String toString() {
return "Student{name='" + name + "', score=" + score + "}";
}
}
public class ComparablePriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Student> studentQueue = new PriorityQueue<>();
studentQueue.offer(new Student("Alice", 88));
studentQueue.offer(new Student("Bob", 92));
studentQueue.offer(new Student("Charlie", 85));
System.out.println("학생 성적 우선순위 큐:");
while (!studentQueue.isEmpty()) {
System.out.println(studentQueue.poll());
}
}
}3. 람다식 이용
람다식을 사용하여 우선순위를 설정할 수 있다. 이번에는 주문의 중요도를 기준으로 우선순위를 설정
import java.util.PriorityQueue;
class Order {
int id;
int priority;
public Order(int id, int priority) {
this.id = id;
this.priority = priority;
}
@Override
public String toString() {
return "Order{id=" + id + ", priority=" + priority + "}";
}
}
public class LambdaPriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Order> orderQueue = new PriorityQueue<>((o1, o2) -> o2.priority - o1.priority); // 중요도 기준으로 내림차순 정렬
orderQueue.offer(new Order(1, 3));
orderQueue.offer(new Order(2, 1));
orderQueue.offer(new Order(3, 2));
System.out.println("주문 중요도 우선순위 큐:");
while (!orderQueue.isEmpty()) {
System.out.println(orderQueue.poll());
}
}
}4. Comparator 이용
Comparator를 이용하여 우선순위를 설정할 수 있다. 이번에는 이벤트의 긴급도를 기준으로 우선순위를 설정
아니면 타임스탬프를 활용하여 생성된 이벤트를 시간 순서대로 효과적으로 처리할 수 있을 듯 하다
import java.util.PriorityQueue;
import java.util.Comparator;
class Event {
String name;
int urgency; // 긴급도
public Event(String name, int urgency) {
this.name = name;
this.urgency = urgency;
}
@Override
public String toString() {
return "Event{name='" + name + "', urgency=" + urgency + "}";
}
}
public class ComparatorPriorityQueueExample {
public static void main(String[] args) {
PriorityQueue<Event> eventQueue = new PriorityQueue<>(new Comparator<Event>() {
@Override
public int compare(Event e1, Event e2) {
return Integer.compare(e2.urgency, e1.urgency); // 긴급도 기준으로 내림차순 정렬
}
});
eventQueue.offer(new Event("Meeting", 2));
eventQueue.offer(new Event("Deadline", 5));
eventQueue.offer(new Event("Appointment", 1));
System.out.println("이벤트 긴급도 우선순위 큐:");
while (!eventQueue.isEmpty()) {
System.out.println(eventQueue.poll());
}
}
}PriorityQueue의 주요 메서드를 표로 정리
| 메서드 | 역할 | 동작 및 반환값 | NullPointerException 발생 여부 |
offer(E e) |
큐에 요소를 추가 | 성공적으로 추가되면 true 반환, 실패 시 false 반환 |
e가 null일 때 발생 |
add(E e) |
큐에 요소를 추가 | offer와 동일하게 동작하며 항상 true 반환 |
e가 null일 때 발생 |
peek() |
큐의 머리 요소를 반환 (제거하지 않음) | 큐가 비어있으면 null 반환, 그렇지 않으면 머리 요소 반환 |
없음 |
poll() |
큐의 머리 요소를 반환하고 제거 | 큐가 비어있으면 null 반환, 그렇지 않으면 머리 요소 반환 |
없음 |
remove(Object o) |
큐에서 특정 요소를 제거 | 요소가 제거되면 true 반환, 요소가 없으면 false 반환 |
o가 null일 때 발생 |
clear() |
큐의 모든 요소를 제거 | 큐를 비우고 아무 것도 반환하지 않음 | 없음 |
size() |
큐의 요소 개수 반환 | 현재 큐에 있는 요소의 개수 반환 | 없음 |
isEmpty() |
큐가 비어있는지 확인 | 큐가 비어있으면 true 반환, 그렇지 않으면 false 반환 |
없음 |
아래 표는 Java의 PriorityQueue에 대해 예상할 수 있는 면접 질문들과 그에 대한 답변을 포함한 정보를 표로 정리.
| 질문 | 답변 | 꼬리 질문 | 꼬리 질문 답변 |
1. PriorityQueue란 무엇인가요? |
PriorityQueue는 요소들이 자연스러운 순서나 제공된 Comparator에 따라 정렬되는 큐입니다. 기본적으로 우선순위가 높은 요소가 먼저 큐에서 제거됩니다. |
1. PriorityQueue의 기본 정렬 기준은 무엇인가요? |
PriorityQueue의 기본 정렬 기준은 요소가 구현한 Comparable 인터페이스에 의해 정의됩니다. 만약 Comparator가 제공되지 않았다면, 요소들의 자연스러운 순서에 따라 정렬됩니다. |
2. Comparator를 사용하는 이유는 무엇인가요? |
Comparator를 사용하면 요소들의 자연스러운 순서와 다르게 정렬할 수 있습니다. 이는 특정 요구사항에 맞는 커스텀 정렬 기준을 적용할 수 있도록 도와줍니다. |
||
3. PriorityQueue의 내부 구조는 어떻게 되어 있나요? |
PriorityQueue는 최소 힙(min-heap) 구조를 기반으로 구현되어 있으며, 요소들이 완전 이진 트리의 형태로 저장됩니다. |
||
| 4. 다른 큐와의 차이점은 무엇인가요? | 일반 큐는 FIFO(First-In-First-Out) 방식으로 동작하지만, PriorityQueue는 우선순위에 따라 요소를 처리합니다. |
||
5. PriorityQueue에서 동등한 우선순위를 가진 요소들은 어떻게 처리되나요? |
동등한 우선순위를 가진 요소들은 삽입 순서에 따라 처리되지 않으며, 특정 순서가 보장되지 않습니다. | ||
2. PriorityQueue의 시간 복잡도는 어떻게 되나요? |
PriorityQueue에서 삽입과 제거 연산의 시간 복잡도는 O(log n)입니다. |
1. 삽입과 제거 연산이 O(log n)인 이유는 무엇인가요? | PriorityQueue는 힙 자료구조를 기반으로 하기 때문에 삽입 및 제거 시 트리의 높이(log n)에 비례하는 재배치 연산이 필요합니다. |
| 2. 다른 큐에서의 삽입과 제거 연산 시간 복잡도와 비교해 보세요. | 일반적인 큐에서는 삽입과 제거 연산의 시간 복잡도는 O(1)입니다. 그러나 PriorityQueue에서는 요소들의 정렬 유지가 필요하므로 O(log n) 시간이 소요됩니다. |
||
| 3. 최악의 시간 복잡도는 언제 발생하나요? | 최악의 시간 복잡도는 요소가 트리의 루트 또는 가장 아래에 삽입되거나 제거될 때 발생합니다. 이 경우 트리의 전체 재정렬이 필요할 수 있습니다. | ||
4. PriorityQueue의 전체 트리 구조의 높이는 어떻게 결정되나요? |
트리의 높이는 삽입된 요소의 개수 n에 대해 log n의 높이를 가집니다. | ||
5. PriorityQueue에서 탐색 연산의 시간 복잡도는 어떻게 되나요? |
PriorityQueue는 힙 구조이므로 특정 요소를 탐색하는 시간 복잡도는 O(n)입니다. |
||
3. PriorityQueue는 thread-safe한가요? |
기본적으로 PriorityQueue는 thread-safe하지 않습니다. |
1. PriorityQueue를 thread-safe하게 사용하려면 어떻게 해야 하나요? |
PriorityQueue를 thread-safe하게 사용하려면 외부에서 동기화 블록을 사용하거나, PriorityBlockingQueue와 같은 thread-safe한 대안을 사용할 수 있습니다. |
2. PriorityQueue의 thread-safe하지 않은 이유는 무엇인가요? |
PriorityQueue는 내부적으로 동기화를 제공하지 않으므로, 다중 스레드 환경에서 동시 접근이 일어날 경우 데이터 일관성이 보장되지 않습니다. |
||
3. PriorityQueue와 비슷하지만 thread-safe한 클래스는 무엇이 있나요? |
PriorityBlockingQueue는 PriorityQueue와 유사하지만 thread-safe한 대안입니다. |
||
4. ConcurrentModificationException은 언제 발생하나요? |
PriorityQueue를 반복(iteration)하는 도중 구조가 변경되면 ConcurrentModificationException이 발생할 수 있습니다. |
||
5. 동기화된 환경에서 PriorityQueue를 사용할 때 주의해야 할 점은 무엇인가요? |
동기화된 환경에서는 모든 접근이 동기화 블록 내에서 이루어지도록 해야 하며, 반복 중 구조 변경을 피해야 합니다. | ||
4. PriorityQueue에서 null 요소를 허용하나요? |
아니요, PriorityQueue는 null 요소를 허용하지 않습니다. |
1. 왜 PriorityQueue에서 null을 허용하지 않을까요? |
null 요소가 있으면 정렬 및 우선순위 비교에서 예외가 발생할 수 있기 때문에 허용되지 않습니다. |
| 2. null 요소를 허용하는 자료구조는 무엇이 있나요? | LinkedList, ArrayList와 같은 일부 자료구조는 null 요소를 허용합니다. |
||
| 3. null을 추가하려고 하면 어떤 예외가 발생하나요? | PriorityQueue에 null을 추가하려고 하면 NullPointerException이 발생합니다. |
||
4. null을 허용하기 위해 PriorityQueue를 어떻게 수정할 수 있을까요? |
PriorityQueue 자체를 수정하기보다는, null 대신 특정한 최소값 객체를 사용하는 것이 일반적입니다. |
||
5. null 요소를 허용하지 않는 것이 PriorityQueue의 성능에 어떤 영향을 미칠까요? |
null 요소를 허용하지 않음으로써 비교 연산에서 발생할 수 있는 예외를 방지하고, 전체적인 성능 저하를 피할 수 있습니다. | ||
5. PriorityQueue에 사용자 정의 객체를 삽입하려면 어떻게 해야 하나요? |
사용자 정의 객체를 삽입하려면 해당 객체가 Comparable 인터페이스를 구현하거나 Comparator를 제공해야 합니다. |
1. Comparable과 Comparator의 차이점은 무엇인가요? |
Comparable은 객체 자신이 비교 방법을 정의하는 반면, Comparator는 외부에서 비교 방법을 정의할 수 있습니다. |
2. Comparable 인터페이스를 어떻게 구현하나요? |
Comparable 인터페이스를 구현하려면 compareTo 메서드를 오버라이드하여 객체 간의 비교 방법을 정의합니다. |
||
3. Comparator를 사용하는 방법을 설명해 주세요. |
Comparator는 비교 로직을 정의한 객체를 생성하여 PriorityQueue의 생성자에 전달하거나, 람다식을 이용해 비교 방법을 직접 정의할 수 있습니다. |
||
4. PriorityQueue에서 사용자 정의 정렬 기준이 필요할 때는 언제인가요? |
사용자 정의 정렬 기준은 객체의 자연스러운 순서와 다른 기준으로 정렬해야 할 때 필요합니다. 예를 들어, 여러 필드를 기준으로 복합 정렬을 할 경우가 있습니다. | ||
| 5. 두 개의 사용자 정의 객체가 동등한 우선순위를 가질 때 어떻게 처리되나요? | 동등한 우선순위를 가진 경우, PriorityQueue는 특정 순서를 보장하지 않으며, 두 객체의 삽입 순서가 유지되지 않을 수 있습니다. |
우선순위 큐를 좀 더 확인하면서 알게된 부분을 정리하면 다음과 같다.
- thread-safe 하지 않기 때문에 멀티 스레드 환경에서는
PriorityBlockingQueue를 사용해야 한다. - 만약 분산 환경에서 우선순위 큐와 유사한 기능이 필요하다면, Apache Kafka 등의 메시지 큐 서비스나, Redis의 Sorted Set과 같은 분산 데이터 구조를 사용하는 것이 더 적합하다.
반응형
