PriorityQueue(우선순위 큐) 클래스 사용법 & 예제 총정리

1. PriorityQueue(우선순위 큐) 클래스 소개

우선순위 큐는 데이터의 처리 순서를 우선순위에 따라 결정하는 자료구조입니다. 일반적인 큐와 달리, 우선순위가 높은 요소가 먼저 처리되는 특징이 있습니다. Java에서는 PriorityQueue 클래스를 제공하여 우선순위 큐를 구현할 수 있습니다.

PriorityQueue 클래스의 특징

• 우선순위에 따라 요소를 정렬하고 관리합니다.
• 내부에서 이진 힙(binary heap)을 사용하여 요소를 저장합니다. 이진 힙은 부모 노드가 자식 노드보다 항상 우선순위가 높은 완전 이진 트리입니다.
• 요소는 기본적으로 Comparable 인터페이스를 구현한 객체에 의해 정렬됩니다. Comparable 인터페이스를 구현하지 않은 경우, 요소를 추가할 때 Comparator 인터페이스를 사용하여 우선순위를 지정할 수 있습니다.
• 중복된 요소를 허용하며, 중복된 요소를 추가할 수 있습니다. 단, 중복된 요소가 제거되는 작업을 직접 처리해야 합니다.

PriorityQueue 클래스의 활용 방법

1. PriorityQueue 객체를 생성합니다.
2. 요소를 추가할 때는 offer() 메서드를 사용합니다. 이 메서드는 요소를 우선순위에 맞게 정렬하여 적절한 위치에 삽입합니다.
3. 우선순위가 가장 높은 요소를 가져오고 싶을 때는 poll() 메서드를 사용합니다. 이 메서드는 우선순위가 가장 높은 요소를 제거하고 반환합니다.
4. 우선순위가 가장 높은 요소를 확인하고 싶을 때는 peek() 메서드를 사용합니다. 이 메서드는 우선순위가 가장 높은 요소를 반환하지만, 제거하지는 않습니다.
5. 우선순위 큐의 크기를 반환하고 싶을 때는 size() 메서드를 사용합니다.

PriorityQueue 클래스는 다양한 상황에서 사용될 수 있으며, 작업 스케줄링, 이벤트 처리, 최소 신장 트리 알고리즘 등에 활용될 수 있습니다. 다음 항목에서는 PriorityQueue 클래스의 생성 및 초기화 방법에 대해 자세히 알아보겠습니다.

1. 우선순위 큐 개념 설명

우선순위 큐는 데이터를 저장하고 관리하는 자료구조로, 요소의 처리 순서를 우선순위에 따라 결정하는 특징을 가지고 있습니다. 일반적인 큐와는 달리, 우선순위가 높은 요소가 먼저 처리되는 특징을 가지고 있습니다.

데이터를 삽입할 때는 우선순위에 맞게 정렬하여 삽입하고, 데이터를 제거할 때는 우선순위가 가장 높은 데이터를 먼저 제거합니다. 이렇게 우선순위에 따라 처리하는 것은 다양한 상황에서 유용합니다. 예를 들어, 작업 스케줄링에서는 우선순위가 높은 작업을 먼저 처리하고, 이벤트 처리에서는 우선순위가 높은 이벤트를 우선적으로 처리하는 등의 상황에서 활용됩니다.

우선순위 큐는 내부적으로 이진 힙(binary heap)이라는 자료구조를 사용하여 구현됩니다. 이진 힙은 부모 노드가 자식 노드보다 우선순위가 높은 완전 이진 트리입니다. 따라서 요소의 추가나 제거 시간 복잡도는 O(log N)입니다.

Java에서는 PriorityQueue 클래스를 제공하여 우선순위 큐를 쉽게 구현할 수 있습니다. PriorityQueue 클래스는 요소의 추가, 제거, 조회 등의 다양한 기능을 제공하며, 우선순위를 지정하거나 요소를 비교하는 방식을 선택할 수 있습니다. 다음 항목에서는 PriorityQueue 클래스의 생성 및 초기화 방법에 대해 자세히 알아보겠습니다.

2. PriorityQueue 클래스의 특징과 활용 방법 소개

PriorityQueue 클래스는 Java에서 우선순위 큐를 구현하기 위해 제공되는 클래스입니다. PriorityQueue 클래스는 다음과 같은 특징을 가지고 있습니다.

PriorityQueue 클래스의 특징

• 요소를 우선순위에 따라 정렬하고 관리합니다.
• 내부적으로 이진 힙(binary heap)을 사용하여 요소를 저장합니다. 이진 힙은 부모 노드가 자식 노드보다 항상 우선순위가 높은 완전 이진 트리입니다.
• 기본적으로 Comparable 인터페이스를 구현한 객체에 의해 요소가 정렬됩니다. Comparable 인터페이스를 구현하지 않은 경우, Comparator 인터페이스를 구현한 객체를 사용하여 우선순위를 지정할 수 있습니다.
• 중복된 요소를 허용하고, 중복된 요소를 추가할 수 있습니다. 단, 중복된 요소가 제거되는 작업을 직접 처리해야 합니다.

PriorityQueue 클래스의 활용 방법

1. PriorityQueue 객체를 생성합니다. 아래의 코드와 같이 우선순위 큐를 생성할 수 있습니다.

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

2. 우선순위 큐에 요소를 추가하고 싶을 때는 offer() 메서드를 사용합니다. 우선순위 큐는 요소를 우선순위에 맞게 정렬해야 하기 때문에 offer() 메서드를 사용하여 요소를 삽입합니다.

pq.offer(5);
pq.offer(2);
pq.offer(8);

3. 우선순위가 가장 높은 요소를 가져오고 싶을 때는 poll() 메서드를 사용합니다. poll() 메서드는 우선순위가 가장 높은 요소를 제거하고 반환합니다.

int highestPriority = pq.poll(); // 2

4. 우선순위가 가장 높은 요소를 확인하고 싶을 때는 peek() 메서드를 사용합니다. peek() 메서드는 우선순위가 가장 높은 요소를 반환하지만, 제거하지는 않습니다.

int highestPriority = pq.peek(); // 2

5. 우선순위 큐의 크기를 반환하고 싶을 때는 size() 메서드를 사용합니다. 아래의 코드와 같이 우선순위 큐의 크기를 확인할 수 있습니다.

int size = pq.size();

PriorityQueue 클래스는 다양한 상황에서 활용될 수 있습니다. 예를 들어, 작업 스케줄링, 이벤트 처리, 최소 신장 트리 알고리즘 등에서 우선순위 큐가 활용될 수 있습니다.

2. PriorityQueue 클래스의 특징과 활용 방법 소개

우선순위 큐는 데이터를 저장하고 관리하는 자료구조로, 요소의 처리 순서를 우선순위에 따라 결정하는 특징을 가지고 있습니다. Java에서는 PriorityQueue 클래스를 제공하여 우선순위 큐를 쉽게 구현할 수 있습니다. 아래에서는 PriorityQueue 클래스의 특징과 활용 방법에 대해 상세히 알아보겠습니다.

PriorityQueue 클래스의 특징

1. 요소의 정렬 및 관리: PriorityQueue 클래스는 요소를 우선순위에 따라 정렬하여 저장하고 관리합니다. 이진 힙(binary heap)이라는 자료구조를 내부적으로 사용하여 요소를 저장하며, 부모 노드가 자식 노드보다 우선순위가 높은 완전 이진 트리입니다.

2. Comparable 및 Comparator 인터페이스 지원: PriorityQueue 클래스는 기본적으로 Comparable 인터페이스를 구현한 객체에 의해 요소들이 정렬됩니다. Comparable 인터페이스를 구현하지 않은 경우, Comparator 인터페이스를 구현한 객체를 사용하여 우선순위를 지정할 수 있습니다.

3. 중복된 요소 허용: PriorityQueue 클래스는 중복된 요소를 허용합니다. 따라서 중복된 요소를 추가할 수 있으며, 중복된 요소가 제거되는 작업은 직접 처리해야 합니다.

PriorityQueue 클래스의 활용 방법

1. 우선순위 큐 생성: PriorityQueue 클래스를 사용하여 우선순위 큐 객체를 생성합니다. 아래의 코드와 같이 생성할 수 있습니다.

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

2. 요소 추가: offer() 메서드를 사용하여 우선순위 큐에 요소를 추가합니다. 우선순위가 높은 순서대로 정렬되므로, 정렬이 필요한 경우에는 offer() 메서드를 사용합니다.

   pq.offer(5);
   pq.offer(2);
   pq.offer(8);

3. 우선순위가 가장 높은 요소 제거 및 반환: poll() 메서드를 사용하여 우선순위가 가장 높은 요소를 제거하고 반환합니다.

   int highestPriority = pq.poll(); // 2

4. 우선순위가 가장 높은 요소 확인: peek() 메서드를 사용하여 우선순위가 가장 높은 요소를 확인합니다. 이때, 요소는 제거되지 않습니다.

   int highestPriority = pq.peek(); // 2

5. 큐의 크기 확인: size() 메서드를 사용하여 우선순위 큐의 크기를 확인할 수 있습니다.

   int size = pq.size();

PriorityQueue 클래스는 다양한 상황에서 활용될 수 있습니다. 작업 스케줄링, 이벤트 처리, 최소 신장 트리 알고리즘 등에서 우선순위 큐를 활용할 수 있으며, 효율적인 데이터 관리와 처리를 위해 사용됩니다.

2. PriorityQueue 클래스 생성 및 초기화

PriorityQueue 클래스를 사용하여 우선순위 큐 객체를 생성하고 초기화하는 방법에 대해 알아보겠습니다.

우선순위 큐를 생성하려면 PriorityQueue 클래스의 인스턴스를 만들어야 합니다. PriorityQueue 객체를 생성하는 방법은 아래의 코드와 같습니다.

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

위의 코드는 Integer 타입의 요소를 가지는 우선순위 큐 객체를 생성하는 예시입니다. 우선순위 큐를 다른 타입의 요소로 생성하려면 <E> 대신 해당 타입을 사용하면 됩니다. 예를 들어, 문자열 우선순위 큐를 생성하려면 아래의 코드와 같이 작성합니다.

PriorityQueue<String> pq = new PriorityQueue<>();

이렇게 PriorityQueue 객체를 생성한 후에는 요소를 초기화하고 추가할 수 있습니다. 요소를 추가하는 방법은 offer() 메서드를 사용하는 것입니다. offer() 메서드를 호출하여 요소를 추가하면, 자동으로 우선순위에 따라 정렬됩니다. 아래의 코드는 우선순위 큐에 요소를 추가하는 예시입니다.

pq.offer(5);
pq.offer(2);
pq.offer(8);

위의 코드에서는 숫자 5, 2, 8을 우선순위 큐에 추가하고 있습니다. 요소를 추가하면 우선순위 큐는 자동으로 정렬하여 다음과 같이 요소를 저장합니다.

2, 5, 8

초기화 및 요소 추가를 완료한 뒤에는 우선순위 큐를 활용하여 작업을 수행할 수 있습니다. 위의 코드에서 우선순위 큐 객체 pq를 사용하여 다양한 작업을 진행할 수 있습니다.

- PriorityQueue 객체 생성하기

PriorityQueue 클래스를 사용하여 우선순위 큐 객체를 생성하는 과정에 대해 알아보겠습니다.

우선순위 큐를 생성하려면 PriorityQueue 클래스의 인스턴스를 만들어야 합니다. PriorityQueue 객체를 생성하는 방법은 아래의 코드와 같습니다.

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

위의 코드는 Integer 타입의 요소를 가지는 우선순위 큐 객체를 생성하는 예시입니다. 타입은 <E> 자리에 해당하는 부분에 적절한 타입을 넣어주면 됩니다. 예를 들어, 문자열 우선순위 큐를 생성하려면 아래의 코드와 같이 작성합니다.

PriorityQueue<String> pq = new PriorityQueue<>();

이런 식으로 우선순위 큐 객체를 생성하면, 우선순위 큐가 기본적으로 정렬된 상태로 초기화됩니다.

우선순위 큐 객체를 초기화한 후에는 offer() 메서드를 사용하여 요소를 추가할 수 있습니다. 아래의 코드는 우선순위 큐에 요소를 추가하는 예시입니다.

pq.offer(5);
pq.offer(2);
pq.offer(8);

위의 코드에서는 숫자 5, 2, 8을 우선순위 큐에 추가하고 있습니다. 요소를 추가하면 우선순위 큐는 자동으로 정렬하여 요소를 저장합니다.

이렇게 초기화 및 요소 추가를 완료한 뒤에는 우선순위 큐를 활용하여 다양한 작업을 수행할 수 있습니다. 위의 코드에서 우선순위 큐 객체 pq를 사용하여 다음 작업을 진행할 수 있습니다.

- 우선순위 큐에 요소 추가하기

우선순위 큐에 요소를 추가하는 방법에 대해 알아보겠습니다.

요소를 추가하기 위해서는 offer() 메서드를 사용합니다. 우선순위 큐에 요소를 추가하면, 해당 요소는 우선순위에 따라 자동으로 정렬됩니다.

아래의 코드는 우선순위 큐에 요소를 추가하는 예시입니다.

pq.offer(5);
pq.offer(2);
pq.offer(8);

위의 코드에서는 숫자 5, 2, 8을 우선순위 큐에 추가하고 있습니다. offer() 메서드를 호출하여 각 숫자를 우선순위 큐에 추가하면, 우선순위에 따라 자동으로 정렬됩니다.

그러면 우선순위 큐에 요소가 어떻게 저장되는지 살펴보겠습니다. 위의 코드에서 숫자 5, 2, 8을 추가한 후 우선순위 큐에 저장된 순서는 다음과 같습니다.

2, 5, 8

우선순위 큐의 요소는 작은 값부터 큰 값의 순서로 저장되며, 동일한 우선순위를 가진 요소들은 저장 순서에 따라 정렬됩니다.

따라서, 우선순위 큐에 요소를 추가하기 위해서는 offer() 메서드를 사용하면 됩니다. 이를 통해 우선순위에 따라 자동으로 정렬된 요소들이 저장될 것입니다.

- 우선순위 큐 요소 접근하기

우선순위 큐에 저장된 요소에 접근하는 방법에 대해 알아보겠습니다.

우선순위 큐에서는 가장 우선순위가 높은 요소를 앞쪽에서부터 차례대로 접근할 수 있습니다. 따라서, poll() 메서드를 사용하여 우선순위가 가장 높은 요소를 가져올 수 있습니다. 가져온 요소는 우선순위 큐에서 삭제되며, 다음 우선순위가 높은 요소가 접근 가능해집니다.

아래의 코드는 우선순위 큐에서 요소를 접근하는 예시입니다.

int firstElement = pq.poll();
int secondElement = pq.poll();

위의 코드에서는 우선순위 큐에서 poll() 메서드를 두 번 호출하여 요소를 가져오고 있습니다. 첫 번째 호출은 우선순위가 가장 높은 요소를 가져오고, 두 번째 호출은 다음으로 우선순위가 높은 요소를 가져옵니다. 이렇게 가져온 요소는 우선순위 큐에서 삭제되므로, 다시 poll() 메서드를 호출하면 그 다음 우선순위가 높은 요소가 접근 가능해집니다.

접근한 요소를 활용하기 위해서는 변수에 저장하여 사용하면 됩니다. 위의 코드에서는 firstElement 변수와 secondElement 변수에 각각 첫 번째와 두 번째로 가져온 요소가 저장됩니다.

따라서, 우선순위 큐에서 요소를 접근하기 위해서는 poll() 메서드를 사용하여 우선순위가 가장 높은 요소를 가져오면 됩니다. 이렇게 접근한 요소는 사용자가 원하는 방식으로 활용할 수 있습니다.

- 우선순위 큐 요소 접근하기

우선순위 큐에서 요소에 접근하는 방법에 대해 알아보겠습니다.

우선순위 큐는 가장 우선순위가 높은 요소부터 차례대로 접근할 수 있습니다. 이를 위해 poll() 메서드를 사용합니다. poll() 메서드는 우선순위가 가장 높은 요소를 가져오고, 해당 요소는 우선순위 큐에서 삭제됩니다. 그리고 다음으로 우선순위가 높은 요소가 접근 가능해집니다.

아래의 코드는 우선순위 큐에서 요소를 접근하는 예시입니다.

int firstElement = pq.poll();
int secondElement = pq.poll();

위의 예시에서는 poll() 메서드를 두 번 호출하여 요소를 가져오고 있습니다. 첫 번째 호출은 우선순위가 가장 높은 요소를 가져오고, 두 번째 호출은 다음으로 우선순위가 높은 요소를 가져옵니다. 이렇게 가져온 요소는 우선순위 큐에서 삭제되므로, 다시 poll() 메서드를 호출하면 그 다음 우선순위가 높은 요소가 접근 가능해집니다.

접근한 요소를 활용하기 위해서는 변수에 저장하여 사용하면 됩니다. 위의 코드에서는 firstElement 변수와 secondElement 변수에 각각 첫 번째와 두 번째로 가져온 요소가 저장됩니다.

따라서, 우선순위 큐에서 요소를 접근하기 위해서는 poll() 메서드를 사용하여 우선순위가 가장 높은 요소를 가져오면 됩니다. 이렇게 접근한 요소는 사용자가 원하는 방식으로 활용할 수 있습니다.

3. PriorityQueue 클래스의 주요 메서드

PriorityQueue 클래스는 우선순위 큐를 구현한 클래스입니다. 이 클래스에는 여러 가지 주요 메서드가 있습니다. 각 메서드에 대해 자세히 알아보겠습니다.

3.1 add(element) / offer(element)

add(element) 또는 offer(element) 메서드는 우선순위 큐에 요소를 추가하는 역할을 합니다. 이 메서드는 요소를 우선순위에 맞게 정렬하여 큐에 삽입합니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.offer(10);

위의 예시에서는 add()와 offer() 메서드를 사용하여 우선순위 큐에 요소를 추가하고 있습니다. 첫 번째 호출은 5를, 두 번째 호출은 10을 우선순위 큐에 삽입합니다.

3.2 poll()

poll() 메서드는 우선순위 큐에서 가장 우선순위가 높은 요소를 제거하고 가져옵니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(10);
int highestPriority = pq.poll();

위의 예시에서는 poll() 메서드를 호출하여 우선순위 큐에서 가장 우선순위가 높은 요소를 가져오고 있습니다. 이때, 해당 요소는 우선순위 큐에서 제거됩니다. 따라서, highestPriority 변수에는 10이 저장될 것입니다.

3.3 peek()

peek() 메서드는 우선순위 큐에서 가장 우선순위가 높은 요소를 가져오되, 제거하지는 않습니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(10);
int highestPriority = pq.peek();

위의 예시에서는 peek() 메서드를 호출하여 우선순위 큐에서 가장 우선순위가 높은 요소를 가져오고 있습니다. 이때, 해당 요소는 우선순위 큐에서 제거되지 않습니다. 따라서, highestPriority 변수에는 10이 저장될 것입니다.

3.4 remove(element)

remove(element) 메서드는 우선순위 큐에서 특정 요소를 제거합니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(10);
pq.remove(10);

위의 예시에서는 remove() 메서드를 사용하여 우선순위 큐에서 숫자 10을 제거하고 있습니다.

3.5 size()

size() 메서드는 우선순위 큐에 저장된 요소의 개수를 반환합니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(10);
int size = pq.size();

위의 예시에서는 size() 메서드를 호출하여 우선순위 큐에 저장된 요소의 개수를 가져와 변수에 저장하고 있습니다.

우선순위 큐 클래스의 주요 메서드에 대해 알아보았습니다. 이러한 메서드들을 적절히 활용하여 우선순위 큐를 다양한 상황에 맞게 사용할 수 있습니다.

- offer() 메서드: 요소 추가하기

offer() 메서드는 우선순위 큐에 요소를 추가하는 역할을 합니다. 이 메서드는 큐에 요소를 삽입하고, 우선순위에 맞게 요소를 정렬합니다.

사용법

offer() 메서드는 아래와 같이 사용할 수 있습니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(10);

위의 예시에서는 pq라는 이름의 우선순위 큐 객체를 생성하고, offer() 메서드를 사용하여 5와 10이라는 두 개의 요소를 우선순위 큐에 추가하고 있습니다.

작동 원리

offer() 메서드는 새로운 요소를 우선순위 큐에 삽입하고, 내부적으로 요소를 우선순위에 맞게 재정렬합니다. 이 때, 요소를 정렬하는 방식은 우선순위 큐의 구현 방식에 따라 다를 수 있습니다. 보통 우선순위 큐는 이진 힙(Binary Heap) 자료구조를 사용하여 구현됩니다. 새로운 요소를 삽입했을 때, 우선순위에 따라 요소를 재배치하여 힙의 규칙을 유지합니다.

예를 들어, 우선순위 큐에 요소를 삽입하는 과정은 아래와 같습니다.

1. 새로운 요소를 큐의 끝에 추가합니다.
2. 요소를 상위 노드와 비교하여 우선순위에 맞추어 재배치합니다.
3. 필요에 따라 요소들의 위치를 바꿔가며 힙의 규칙(우선순위 순서)을 유지합니다.
4. 큐에 요소가 추가되면 큐의 크기가 늘어나고, 요소들의 재배치가 필요하므로, 작업의 시간 복잡도는 O(logN)입니다.

반환값

offer() 메서드는 오류가 발생하지 않고 항상 true를 반환합니다. 따라서, 별도의 예외 처리나 반환 결과를 확인할 필요가 없습니다. 만약 우선순위 큐의 크기가 제한되어 있는 경우(maximum capacity), 요소를 추가하지 못할 때 false를 반환하는 경우도 있을 수 있습니다.

offer() 메서드를 사용하여 요소를 우선순위 큐에 추가할 때는, 우선순위에 따라 요소가 정렬되고 큐에 삽입된다는 점을 유의해야 합니다. 이를 통해 우선순위 큐의 기능을 효과적으로 활용할 수 있습니다.

- poll() 메서드: 우선순위가 가장 높은 요소 제거하기

poll() 메서드는 우선순위 큐에서 가장 우선순위가 높은 요소를 제거하고 반환합니다.

사용법

poll() 메서드는 아래와 같이 사용할 수 있습니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(10);
int highestPriority = pq.poll();

위의 예시에서는 pq라는 이름의 우선순위 큐 객체를 생성하고, offer() 메서드를 사용하여 5와 10을 우선순위 큐에 추가하고 있습니다. 그리고 poll() 메서드를 호출하여 가장 우선순위가 높은 요소를 가져옵니다. 이때, 해당 요소는 우선순위 큐에서 제거됩니다.

작동 원리

poll() 메서드는 우선순위 큐에서 가장 우선순위가 높은 요소를 반환하고, 해당 요소를 큐에서 제거합니다. 내부적으로는 힙에서 최상위 노드(가장 우선순위가 높은 요소)를 제거하도록 구현됩니다.

예를 들어, 우선순위 큐에 poll() 메서드를 호출하는 과정은 아래와 같습니다.

1. 우선순위 큐에서 가장 우선순위가 높은 요소(최상위 노드)를 가져옵니다.
2. 최상위 노드를 제거합니다.
3. 요소들의 위치를 재배치하여 힙의 규칙(우선순위 순서)를 유지합니다.
4. 큐에서 요소가 제거되면 큐의 크기가 감소하고, 요소들의 재배치가 필요하므로, 작업의 시간 복잡도는 O(logN)입니다.

반환값

poll() 메서드는 우선순위가 가장 높은 요소를 반환하고, 해당 요소가 큐에서 제거되므로 더 이상 해당 요소를 사용할 수 없습니다. 반환되는 요소의 타입은 우선순위 큐가 지정한 타입과 동일합니다. 만약 우선순위 큐가 비어있다면, null을 반환합니다.

poll() 메서드를 사용하면 지정된 우선순위에 따라 요소가 제거되는 특징을 활용하여 우선순위 큐를 효과적으로 관리할 수 있습니다. 이를 통해 우선순위 큐의 임의의 요소를 제거하는데 사용할 수 있습니다.

- peek() 메서드: 우선순위가 가장 높은 요소 반환하기

peek() 메서드는 우선순위 큐에서 가장 우선순위가 높은 요소를 제거하지 않고 반환합니다.

사용법

peek() 메서드는 아래와 같이 사용할 수 있습니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(10);
int highestPriority = pq.peek();

위의 예시에서는 pq라는 이름의 우선순위 큐 객체를 생성하고, offer() 메서드를 사용하여 5와 10을 우선순위 큐에 추가하고 있습니다. 그리고 peek() 메서드를 호출하여 가장 우선순위가 높은 요소를 가져옵니다. 이때, 해당 요소는 우선순위 큐에서 제거되지 않습니다.

작동 원리

peek() 메서드는 우선순위 큐에서 가장 우선순위가 높은 요소(힙의 최상위 노드)를 반환하고, 해당 요소를 큐에서 제거하지 않습니다. 내부적으로는 힙의 최상위 노드를 가져올 뿐이므로, 큐의 상태는 변경되지 않습니다.

반환값

peek() 메서드는 우선순위가 가장 높은 요소를 반환합니다. 해당 요소는 큐에서 제거되지 않으므로 여전히 큐에서 사용할 수 있습니다. 반환되는 요소의 타입은 우선순위 큐가 지정한 타입과 동일합니다. 만약 우선순위 큐가 비어있다면, null을 반환합니다.

peek() 메서드를 사용하면 우선순위 큐에서 현재 가장 우선순위가 높은 요소를 확인할 수 있습니다. 이를 통해 요소를 제거하지 않고도 우선순위 큐의 상태를 확인할 수 있습니다.

- size() 메서드: 우선순위 큐의 크기 반환하기

size() 메서드는 우선순위 큐에 저장된 요소의 개수를 반환합니다.

사용법

size() 메서드는 아래와 같이 사용할 수 있습니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(10);
int size = pq.size();

위의 예시에서는 pq라는 이름의 우선순위 큐 객체를 생성하고, offer() 메서드를 사용하여 5와 10을 우선순위 큐에 추가하고 있습니다. 그리고 size() 메서드를 호출하여 우선순위 큐의 크기를 반환받습니다.

작동 원리

size() 메서드는 우선순위 큐에 저장된 요소의 개수를 반환합니다. 내부적으로는 배열, 리스트 등의 자료구조를 사용하여 저장되는 요소들을 관리하고 있으므로, 해당 자료구조에 저장된 요소의 개수를 반환하게 됩니다.

반환값

size() 메서드는 우선순위 큐에 저장된 요소의 개수를 반환합니다. 반환되는 값의 타입은 정수형입니다.

size() 메서드를 사용하면 우선순위 큐의 크기를 알 수 있습니다. 이를 통해 우선순위 큐에 저장된 요소의 개수를 확인할 수 있으며, 크기에 따라 적절한 조건을 설정하여 작업을 수행할 수 있습니다.

- size() 메서드: 우선순위 큐의 크기 반환하기

size() 메서드는 우선순위 큐에 저장된 요소의 개수를 반환합니다.

사용법

size() 메서드는 아래와 같이 사용할 수 있습니다.

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(10);
int size = pq.size();

위의 예시에서는 pq라는 이름의 우선순위 큐 객체를 생성하고, add() 메서드를 사용하여 5와 10을 우선순위 큐에 추가하고 있습니다. 그리고 size() 메서드를 호출하여 우선순위 큐의 크기를 반환받습니다.

작동 원리

size() 메서드는 우선순위 큐에 저장된 요소의 개수를 반환합니다. 내부적으로는 배열, 리스트 등의 자료구조를 사용하여 저장되는 요소들을 관리하고 있으므로, 해당 자료구조에 저장된 요소의 개수를 반환하게 됩니다.

반환값

size() 메서드는 우선순위 큐에 저장된 요소의 개수를 반환합니다. 반환되는 값의 타입은 정수형입니다.

size() 메서드를 사용하면 우선순위 큐의 크기를 알 수 있습니다. 이를 통해 우선순위 큐에 저장된 요소의 개수를 확인할 수 있으며, 크기에 따라 적절한 조건을 설정하여 작업을 수행할 수 있습니다.

4. 우선순위 설정하기

우선순위 큐에서는 요소들이 우선순위에 따라 정렬되어 저장되는데, 이 때 우선순위를 어떻게 설정할 수 있는지 알아보겠습니다.

Comparator 인터페이스를 사용한 우선순위 설정

Java에서는 Comparator 인터페이스를 이용하여 우선순위를 설정할 수 있습니다. Comparator 인터페이스는 compare() 메서드를 정의하여 요소들의 우선순위를 비교하는 기준을 정할 수 있습니다.

다음은 Comparator 인터페이스를 사용하여 우선순위를 설정하는 방법입니다.

PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
pq.offer(5);
pq.offer(10);

위의 예시에서는 PriorityQueue 객체 pq를 생성할 때 Comparator.reverseOrder()를 전달하였습니다. 이는 우선순위 큐의 요소들을 역순으로 정렬하겠다는 의미입니다. 따라서, 5보다 10이 우선순위가 높게 설정될 것입니다.

Comparable 인터페이스를 이용한 우선순위 설정

우선순위 큐의 요소로 사용되는 객체가 이미 Comparable 인터페이스를 구현한 경우에는 별도의 Comparator 객체를 사용하지 않고도 우선순위를 설정할 수 있습니다. Comparable 인터페이스는 compareTo() 메서드를 정의하여 요소들 간의 우선순위 비교 기준을 제공합니다.

다음은 Comparable 인터페이스를 사용하여 우선순위를 설정하는 방법입니다.

public class Person implements Comparable<Person> {
    private String name;
    private int age;

    // 생성자, getter, setter 등 생략

    @Override
    public int compareTo(Person other) {
        return Integer.compare(this.age, other.age);
    }
}

위의 예시에서는 Person 클래스가 Comparable 인터페이스를 구현하고 있습니다. compareTo() 메서드를 오버라이딩하여 나이에 따라 우선순위를 비교하도록 설정하였습니다.

PriorityQueue<Person> pq = new PriorityQueue<>();
Person person1 = new Person("John", 30);
Person person2 = new Person("Alice", 25);
pq.offer(person1);
pq.offer(person2);

위의 코드에서는 Person 객체를 요소로 갖는 우선순위 큐를 생성한 후, Person 객체들을 우선순위를 고려하여 추가하고 있습니다. compareTo() 메서드를 통해 우선순위가 결정되며, 나이가 낮은 Alice가 나이가 높은 John보다 우선순위가 높게 설정될 것입니다.

우선순위를 설정하는 방법에는 Comparator 인터페이스와 Comparable 인터페이스를 사용하는 두 가지 방법이 있습니다. 상황에 맞게 선택하여 우선순위를 설정할 수 있으며, 이를 통해 우선순위 큐의 동작을 유연하게 조정할 수 있습니다.

Comparator 인터페이스 사용해서 우선순위 설정하기

Java에서는 Comparator 인터페이스를 사용하여 우선순위를 설정할 수 있습니다. Comparator 인터페이스는 compare() 메서드를 정의하여 요소들의 우선순위를 비교하는 기준을 설정합니다.

Comparator 인터페이스 구현하기

Comparator 인터페이스를 사용하기 위해서는 먼저 Comparator 인터페이스를 구현한 클래스를 작성해야 합니다. 이 클래스는 compare() 메서드를 오버라이딩하여 요소들을 비교하는 기준을 정의합니다.

import java.util.Comparator;

public class MyComparator implements Comparator<Integer> {

    @Override
    public int compare(Integer a, Integer b) {
        return Integer.compare(b, a);       // 내림차순 정렬
    }
}

위의 예시에서는 MyComparator 클래스가 Comparator 인터페이스를 구현하고 있습니다. compare() 메서드를 오버라이딩하여 두 개의 정수를 비교하고 있으며, 이 때 뒤의 정수가 앞의 정수보다 큰 경우에 음수를 반환하여 내림차순으로 정렬하도록 설정하였습니다.

정의된 Comparator 객체를 우선순위 큐에 전달하기

이제 구현한 Comparator 인터페이스를 이용하여 우선순위를 설정할 수 있습니다. 우선순위 큐 객체를 생성할 때, 생성자에 Comparator 객체를 전달하여 우선순위 설정을 지정할 수 있습니다.

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(new MyComparator());
        pq.offer(5);
        pq.offer(10);
        pq.offer(3);

        // 출력 결과: 10 5 3
        while (!pq.isEmpty()) {
            System.out.print(pq.poll() + " ");
        }
    }
}

위의 예시에서는 MyComparator 객체를 생성하여 PriorityQueue 객체 pq의 생성자에 전달하고 있습니다. 이렇게 함으로써 요소들은 MyComparator의 compare() 메서드에 의해 비교되며, 내림차순으로 정렬된 상태로 저장되게 됩니다.

pq.offer(5)와 pq.offer(10)을 수행한 후, poll() 메서드를 이용하여 요소들을 하나씩 빼내어 출력하면, 10, 5, 3의 순서로 요소들이 출력될 것입니다.

위의 방법처럼 Comparator 인터페이스를 구현한 클래스를 작성하여 우선순위를 설정하고, PriorityQueue 생성자에 전달함으로써 우선순위 큐의 동작을 원하는 대로 설정할 수 있습니다.

Comparable 인터페이스를 구현한 클래스 사용해서 우선순위 설정하기

우선순위 큐에서는 Comparable 인터페이스를 구현한 클래스를 사용하여 우선순위를 설정할 수 있습니다. Comparable 인터페이스는 compareTo() 메서드를 오버라이딩하여 요소들을 비교하는 기준을 제공합니다.

Comparable 인터페이스 구현하기

Comparable 인터페이스를 사용하기 위해서는 먼저 Comparable 인터페이스를 구현한 클래스를 작성해야 합니다. 이 클래스는 compareTo() 메서드를 오버라이딩하여 요소들을 비교하는 기준을 정의합니다.

다음은 Person 클래스를 예시로 Comparable 인터페이스를 구현한 코드입니다.

public class Person implements Comparable<Person> {
    private String name;
    private int age;

    // 생성자, getter, setter 등 생략

    @Override
    public int compareTo(Person other) {
        return Integer.compare(this.age, other.age);
    }
}

위의 예시에서는 Person 클래스가 Comparable 인터페이스를 구현하고 있습니다. compareTo() 메서드를 오버라이딩하여 나이에 따라 우선순위를 비교하는 기준을 정의하고 있습니다.

Comparable 인터페이스를 적용한 우선순위 큐

Comparable 인터페이스를 구현한 클래스를 사용하여 우선순위를 설정할 수 있습니다. 우선순위 큐 객체를 생성할 때, 추가되는 요소들의 클래스가 Comparable 인터페이스를 구현한 클래스일 경우, 요소들은 compareTo() 메서드를 이용하여 자동으로 우선순위가 결정됩니다.

다음은 Person 객체를 요소로 갖는 우선순위 큐를 생성하고, Person 객체들을 우선순위를 고려하여 추가하는 예시입니다.

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Person> pq = new PriorityQueue<>();
        Person person1 = new Person("John", 30);
        Person person2 = new Person("Alice", 25);
        pq.offer(person1);
        pq.offer(person2);

        // 출력 결과: 25 30
        while (!pq.isEmpty()) {
            System.out.print(pq.poll().getAge() + " ");
        }
    }
}

위의 코드에서는 Person 객체를 요소로 갖는 우선순위 큐를 생성한 후, Person 객체들을 우선순위를 고려하여 추가하고 있습니다. getAge() 메서드를 통해 나이 정보를 가져와 출력하였으며, 이를 보면 나이가 낮은 Alice가 나이가 높은 John보다 우선순위가 높게 설정되어 있음을 알 수 있습니다.

Comparable 인터페이스를 구현한 클래스를 사용하여 우선순위를 설정하고, PriorityQueue에 요소를 추가함으로써 우선순위 큐의 동작을 원하는 대로 설정할 수 있습니다. Comparable 인터페이스를 이용하면 우선순위 설정에 더욱 편리하게 접근할 수 있습니다.

Comparable 인터페이스를 구현한 클래스 사용해서 우선순위 설정하기

우선순위 큐에서는 Comparable 인터페이스를 구현한 클래스를 사용하여 우선순위를 설정할 수 있습니다. Comparable 인터페이스는 compareTo() 메서드를 오버라이딩하여 요소들을 비교하는 기준을 제공합니다.

Comparable 인터페이스 구현하기

Comparable 인터페이스를 사용하기 위해서는 먼저 Comparable 인터페이스를 구현한 클래스를 작성해야 합니다. 이 클래스는 compareTo() 메서드를 오버라이딩하여 요소들을 비교하는 기준을 정의합니다.

예를 들어, 사람(Person)을 표현하는 클래스를 Comparable 인터페이스를 구현하여 우선순위 설정을 할 수 있습니다.

public class Person implements Comparable<Person> {
    private String name;
    private int age;

    // 생성자, getter, setter 등 생략

    @Override
    public int compareTo(Person other) {
        return Integer.compare(this.age, other.age);
    }
}

위의 예시에서는 Person 클래스가 Comparable 인터페이스를 구현하고 있습니다. compareTo() 메서드를 오버라이딩하여 나이에 따라 우선순위를 비교하는 기준을 정의하고 있습니다. 이 경우에는 나이가 적은 사람이 우선순위가 높게 설정되도록 정의되어 있습니다.

Comparable 인터페이스를 적용한 우선순위 큐

Comparable 인터페이스를 구현한 클래스를 사용하여 우선순위를 설정할 수 있습니다. 우선순위 큐 객체를 생성할 때, 추가되는 요소들의 클래스가 Comparable 인터페이스를 구현한 클래스일 경우, 요소들은 compareTo() 메서드를 이용하여 자동으로 우선순위가 결정됩니다.

다음은 Person 객체를 요소로 갖는 우선순위 큐를 생성하고, Person 객체들을 우선순위를 고려하여 추가하는 예시입니다.

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Person> pq = new PriorityQueue<>();
        Person person1 = new Person("John", 30);
        Person person2 = new Person("Alice", 25);
        pq.offer(person1);
        pq.offer(person2);

        // 출력 결과: 25 30
        while (!pq.isEmpty()) {
            System.out.print(pq.poll().getAge() + " ");
        }
    }
}

위의 코드에서는 Person 객체를 요소로 갖는 우선순위 큐를 생성한 후, Person 객체들을 우선순위를 고려하여 추가하고 있습니다. getAge() 메서드를 통해 나이 정보를 가져와 출력하였으며, 이를 보면 나이가 낮은 Alice가 나이가 높은 John보다 우선순위가 높게 설정되어 있음을 알 수 있습니다.

Comparable 인터페이스를 구현한 클래스를 사용하여 우선순위를 설정하고, PriorityQueue에 요소를 추가함으로써 우선순위 큐의 동작을 원하는 대로 설정할 수 있습니다. Comparable 인터페이스를 이용하면 우선순위 설정에 더욱 편리하게 접근할 수 있습니다.

5. 우선순위 큐 활용 예제

우선순위 큐는 데이터들을 우선순위에 따라 저장하고, 우선순위가 가장 높은 데이터가 가장 먼저 처리되는 자료구조입니다. 우선순위 큐는 다양한 애플리케이션에서 사용될 수 있으며, 이번 예제에서는 우선순위 큐가 어떻게 활용되는지 알아보겠습니다.

요구사항

우선순위 큐를 사용하여 학생들의 성적을 관리하고, 가장 성적이 높은 학생을 출력하는 프로그램을 작성해야 합니다. 각 학생(student)은 이름(name)과 성적(score) 정보를 갖고 있습니다.

해결 방법

해결 방법은 다음과 같습니다.

1. Comparable 인터페이스를 구현한 Student 클래스를 작성합니다. 이 클래스는 이름과 성적을 저장하고, 성적에 따라 우선순위가 결정됩니다.
2. 우선순위 큐(PriorityQueue) 객체를 생성합니다.
3. 학생들의 성적을 우선순위에 따라 우선순위 큐에 추가합니다.
4. 우선순위 큐에서 가장 성적이 높은 학생을 꺼내어 출력합니다.

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Student> pq = new PriorityQueue<>();

        Student student1 = new Student("Alice", 85);
        Student student2 = new Student("Bob", 92);
        Student student3 = new Student("Chris", 78);

        pq.offer(student1);
        pq.offer(student2);
        pq.offer(student3);

        Student topStudent = pq.poll();
        System.out.println("가장 성적이 높은 학생: " + topStudent.getName() + " (성적: " + topStudent.getScore() + ")");
    }
}

class Student implements Comparable<Student> {
    private String name;
    private int score;

    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    public String getName() {
        return name;
    }

    public int getScore() {
        return score;
    }

    @Override
    public int compareTo(Student other) {
        return Integer.compare(other.score, this.score);  // 성적이 높은 순서로 정렬하기 위해 다른 객체와의 비교 결과를 반전함
    }
}

위 코드에서는 Student 클래스를 Comparable 인터페이스를 구현하여 성적을 기준으로 우선순위를 설정합니다. 성적이 높은 학생일수록 우선순위가 높도록 compareTo() 메서드가 구현되어 있습니다.

Main 클래스에서는 우선순위 큐를 생성한 후, 학생 객체들을 우선순위에 따라 추가합니다. 마지막으로 poll() 메서드를 사용하여 가장 성적이 높은 학생을 꺼내어 출력합니다.

출력 결과는 다음과 같습니다.

가장 성적이 높은 학생: Bob (성적: 92)

상기 예시를 통해 우선순위 큐를 활용한 실제 문제를 해결하는 방법을 살펴보았습니다. Comparable 인터페이스를 활용하여 요소들의 우선순위를 설정할 수 있게 되어, 더욱 유연하고 효과적인 자료구조를 구현할 수 있게 되었습니다.

작업 스케줄링 시스템 구현하기

작업 스케줄링 시스템은 여러 작업들을 우선순위에 따라 처리하는 시스템입니다. 이번 예제에서는 작업(job)을 관리하는 작업 스케줄링 시스템을 구현하는 방법을 알아보겠습니다.

요구사항

작업 스케줄링 시스템을 구현하여 다음과 같은 기능을 제공해야 합니다.

• 작업을 추가할 수 있습니다.
• 가장 우선순위가 높은 작업을 실행할 수 있습니다.

해결 방법

해결 방법은 다음과 같습니다.

1. Comparable 인터페이스를 구현한 Job 클래스를 작성합니다. 이 클래스는 작업 이름(name)과 작업의 우선순위(priority) 정보를 갖습니다.
2. 우선순위 큐(PriorityQueue) 객체를 생성합니다.
3. 작업들을 우선순위에 따라 우선순위 큐에 추가합니다.
4. 가장 우선순위가 높은 작업을 꺼내어 실행합니다.

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Job> jobQueue = new PriorityQueue<>();

        Job job1 = new Job("작업1", 2);
        Job job2 = new Job("작업2", 1);
        Job job3 = new Job("작업3", 3);

        jobQueue.offer(job1);
        jobQueue.offer(job2);
        jobQueue.offer(job3);

        Job topJob = jobQueue.poll();
        System.out.println("가장 우선순위가 높은 작업 실행: " + topJob.getName());
    }
}

class Job implements Comparable<Job> {
    private String name;
    private int priority;

    public Job(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    public String getName() {
        return name;
    }

    @Override
    public int compareTo(Job other) {
        return Integer.compare(this.priority, other.priority);
    }
}

위 코드에서는 Job 클래스를 Comparable 인터페이스를 구현하여 우선순위를 기준으로 작업을 관리합니다. Job 클래스는 작업의 이름과 우선순위를 저장하고, compareTo() 메서드를 오버라이딩하여 우선순위를 비교합니다.

Main 클래스에서는 우선순위 큐를 생성한 후, 작업 객체들을 우선순위에 따라 추가합니다. 마지막으로 poll() 메서드를 사용하여 가장 우선순위가 높은 작업을 꺼내어 실행합니다.

출력 결과는 다음과 같습니다.

가장 우선순위가 높은 작업 실행: 작업2

위 예시를 통해 작업 스케줄링 시스템을 구현하는 방법을 살펴보았습니다. Comparable 인터페이스를 사용하여 우선순위를 설정하면 우선순위 큐를 효과적으로 활용할 수 있으며, 작업 스케줄링 시스템을 효율적으로 구현할 수 있습니다.

이벤트 처리 시스템 구현하기

이벤트 처리 시스템은 여러 이벤트들을 우선순위에 따라 처리하는 시스템입니다. 이번 예제에서는 이벤트(event)를 관리하는 이벤트 처리 시스템을 구현하는 방법을 알아보겠습니다.

요구사항

이벤트 처리 시스템을 구현하여 다음과 같은 기능을 제공해야 합니다.

• 이벤트를 추가할 수 있습니다.
• 가장 우선순위가 높은 이벤트를 처리할 수 있습니다.

해결 방법

해결 방법은 다음과 같습니다.

1. Comparable 인터페이스를 구현한 Event 클래스를 작성합니다. 이 클래스는 이벤트 이름(name)과 이벤트의 우선순위(priority) 정보를 갖습니다.
2. 우선순위 큐(PriorityQueue) 객체를 생성합니다.
3. 이벤트들을 우선순위에 따라 우선순위 큐에 추가합니다.
4. 가장 우선순위가 높은 이벤트를 꺼내어 처리합니다.

import java.util.PriorityQueue;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Event> eventQueue = new PriorityQueue<>();

        Event event1 = new Event("이벤트1", 2);
        Event event2 = new Event("이벤트2", 1);
        Event event3 = new Event("이벤트3", 3);

        eventQueue.offer(event1);
        eventQueue.offer(event2);
        eventQueue.offer(event3);

        Event topEvent = eventQueue.poll();
        System.out.println("가장 우선순위가 높은 이벤트 처리: " + topEvent.getName());
    }
}

class Event implements Comparable<Event> {
    private String name;
    private int priority;

    public Event(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    public String getName() {
        return name;
    }

    @Override
    public int compareTo(Event other) {
        return Integer.compare(this.priority, other.priority);
    }
}

위 코드에서는 Event 클래스를 Comparable 인터페이스를 구현하여 우선순위를 기준으로 이벤트를 관리합니다. Event 클래스는 이벤트의 이름과 우선순위를 저장하고, compareTo() 메서드를 오버라이딩하여 우선순위를 비교합니다.

Main 클래스에서는 우선순위 큐를 생성한 후, 이벤트 객체들을 우선순위에 따라 추가합니다. 마지막으로 poll() 메서드를 사용하여 가장 우선순위가 높은 이벤트를 꺼내어 처리합니다.

출력 결과는 다음과 같습니다.

가장 우선순위가 높은 이벤트 처리: 이벤트2

위 예시를 통해 이벤트 처리 시스템을 구현하는 방법을 살펴보았습니다. Comparable 인터페이스를 사용하여 우선순위를 설정하면 우선순위 큐를 효과적으로 활용할 수 있으며, 이벤트 처리 시스템을 효율적으로 구현할 수 있습니다.