우선순위큐
우선순위 큐 (Priority Queue)
우선순위가 높은 데이터가 먼저 나옴 (≠ FIFO)
모든 데이터에 우선순위가 있음
Dequeue 시, 우선순위가 높은 순으로 나감
우선 순위가 같은 경우는 FIFO
우선순위 큐 – enqueue, dequeue
최소 힙 및 최대 힙의 삽입 삭제와 같음
우선순위 큐 - 구현
배열
연결 리스트
힙
비선형 자료구조 - 우선순위 큐
연결 리스트를 이용한 우선순위 큐
자바 기본 PriorityQueue 응용
// 비선형 자료구조 - 우선순위 큐
// 연결 리스트를 이용한 우선순위 큐
// 자바 기본 PriorityQueue
import java.util.*;
public class Main {
public static void enqueue(LinkedList<Integer> list, int data) {
//추가할 데이터, data값이 작을수록 우선순위가 높으니까, 기존 데이터 대배 값이 작으면은, 연결리스트에서 앞쪽으로 추가될수 있게 만들어줌.
int idx = list.size();
for (int i = 0; i < list.size(); i++) {
if (list.get(i) > data) {
idx = i;
break;
}
}
//기존의 리스트는 정렬된 연결리스트 상태이기 때문에, 앞쪽의 값들이 더 작아서, 맨 앞만 새로들어온 data보다 큰지 비교해주고,
//해당되면 idx 업데이트하고, 그 뒤의 값을은 어차피 앞에 있는 데이터들 보단 클테니까, 더 비교할거 없이 break해주면됨.
//break해서 찾은 idx위치에 해당 data 넣어주면 끝!
list.add(idx, data);
}
public static Integer dequeue(LinkedList<Integer> list) {
//얘는 이미 정렬되어 있고, 그 우선순위 큐니까 가장 앞에 있는 데이터를 이제 꺼내주기만 하면됨!
if (list.size() == 0) {
return null;
}
int data = list.get(0);
list.remove(0);
return data;
}
public static void main(String[] args) {
// 연결리스트를 이용한 우선순위 큐
System.out.println("== 연결리스트 방식의 우선순위 큐 ==");
LinkedList<Integer> pqList = new LinkedList();
enqueue(pqList, 5);
enqueue(pqList, 7);
enqueue(pqList, 3);
enqueue(pqList, 1);
enqueue(pqList, 9);
System.out.println(pqList);
System.out.println(dequeue(pqList));
System.out.println(dequeue(pqList));
System.out.println(pqList);
System.out.println();
// 자바 기본 PriorityQueue 사용
System.out.println("== 자바 기본 우선순위 큐 ==");
// 우선순위: 낮은 숫자 순
PriorityQueue<Integer> pq = new PriorityQueue();
pq.add(5);
pq.add(7);
pq.add(3);
pq.add(1);
pq.add(9);
System.out.println(Arrays.toString(pq.toArray()));
// 우선순위: 높은 숫자 순
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());
pq2.add(5);
pq2.add(7);
pq2.add(3);
pq2.add(1);
pq2.add(9);
System.out.println(Arrays.toString(pq2.toArray()));
}
}
== 연결리스트 방식의 우선순위 큐 ==
[1, 3, 5, 7, 9]
1
3
[5, 7, 9]
== 자바 기본 우선순위 큐 ==
[1, 3, 5, 7, 9]
[9, 7, 3, 1, 5]
// Practice 1
// 자바 기본 PriorityQueue 응용
import java.util.Arrays;
import java.util.PriorityQueue;
// 1. 이렇게 하면 에러 발생
//class Person {
// 2. Comparable interface 이용
class Person implements Comparable<Person> {
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
// 필수 오버라이드
@Override
public int compareTo(Person o) {
// 1: 변경 안함
// -1: 변경
// 새롭게 추가하는 데이터가 더 작을 때 변경 (작은 값이 위로 올라감, 오름 차순)
// this.age 방금 들어온 데이터, o.age 이전에 있던 데이터, 이게 좀 헷갈렸음!
// this.age 방금 들어온 데이터가 더 작아야, 이 연산을 만족하지 않아서 -1이 리턴이 되니까
//그때, 이제 변경이 일어나서 오름 차순으로 변경이 되는 케이스.
return this.age >= o.age ? 1 : -1;
// 새롭게 추가하는 데이터가 더 클 때 변경 (큰 값이 위로 올라감, 내림 차순)
// return this.age >= o.age ? -1 : 1;
}
}
public class Practice1 {
public static void solution(String[] name, int[] age) {
PriorityQueue<Person> pq = new PriorityQueue();
for (int i = 0; i < name.length; i++) {
pq.offer(new Person(name[i], age[i]));
}
System.out.println("== 내부 힙 구조 ==");
pq.stream().forEach(x -> System.out.println(x.name + " " + x.age));
System.out.println();
System.out.println("== 실제 출력 순서 ==");
while (!pq.isEmpty()) {
Person p = pq.poll();
System.out.println(p.name + " " + p.age);
}
}
public static void main(String[] args) {
String[] name = {"A", "B", "C", "D", "E"};
int[] age = {30, 20, 45, 62, 35};
solution(name, age);
// 다른 방식
System.out.println();
PriorityQueue<Person> pq2 = new PriorityQueue<>((Person p1, Person p2) -> p1.age >= p2.age ? 1 : -1);
for (int i = 0; i < name.length; i++) {
pq2.offer(new Person(name[i], age[i]));
}
while (!pq2.isEmpty()) {
Person p = pq2.poll();
System.out.println(p.name + " " + p.age);
}
}
}
== 내부 힙 구조 ==
B 20
A 30
C 45
D 62
E 35
== 실제 출력 순서 ==
B 20
A 30
E 35
C 45
D 62
B 20
A 30
E 35
C 45
D 62
문자열 사전식 오름차순
// Practice 2
// 문자열 사전식 오름차순
import java.util.PriorityQueue;
class Person2 {
String name;
int age;
public Person2(String name, int age) {
this.name = name;
this.age = age;
}
}
public class Practice2 {
public static void solution(String[] name, int[] age) {
//name기준으로, 오름차순으로 정렬
//내림차순으로 바꾸고 싶으면 p1, p2 바꿔서 실행하면 됨!
PriorityQueue<Person2> pq = new PriorityQueue<>((Person2 p1, Person2 p2) -> p1.name.compareTo(p2.name));
// 참고
// System.out.println("A".compareTo("B"));
for (int i = 0; i < name.length; i++) {
pq.offer(new Person2(name[i], age[i]));
}
while (!pq.isEmpty()) {
Person2 p = pq.poll();
System.out.println(p.name + " " + p.age);
}
}
public static void main(String[] args) {
String[] name = {"A", "B", "C", "D", "E"};
int[] age = {30, 20, 45, 62, 35};
solution(name, age);
}
}
A 30
B 20
C 45
D 62
E 35
nums 배열에 주어진 정수들 중에서 k 번째로 큰 수를 반환하는 프로그램
// Practice1
// nums 배열에 주어진 정수들 중에서 k 번째로 큰 수를 반환하는 프로그램을 작성하세요.
// 입력 예시
// 입력: 3, 1, 2, 7, 6, 4
// k: 2
// 출력: 6
// 입력: 1, 3, 7, 4, 2, 8, 9
// k: 7
// 출력: 1
import java.util.Arrays;
import java.util.PriorityQueue;
public class Practice1 {
public static int solution1(int[] nums, int k) {
// nums 내의 숫자 기준으로 오름차순 출력하면 되므로 해당 값을 기준으로 pq 에 바로 삽입
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int num : nums) {
pq.offer(num);
if(pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
public static int solution2(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
public static void main(String[] args) {
// Test code
int[] nums = {3, 1, 2, 7, 6, 4};
System.out.println(solution1(nums, 2));
System.out.println(solution2(nums, 2));
System.out.println();
nums = new int[]{1, 3, 7, 4, 2, 8, 9};
System.out.println(solution1(nums, 7));
System.out.println(solution2(nums, 7));
}
}
6
6
1
1
돌의 무게 데이터로 이루어진 정수형 stones 배열이 주어졌을 때 다음의 내용에 따라 프로그램을 작성
// Practice2
// 돌의 무게 데이터로 이루어진 정수형 stones 배열이 주어졌을 때 다음의 내용에 따라 프로그램을 작성하세요.
// 해당 배열로부터 가장 무게가 많이 나가는 돌 두개를 꺼내세요.
// 두 개의 돌을 충돌시키는데, 무게가 같으면 둘다 소멸,
// 무게가 다르면 남은 무게만큼의 돌은 다시 추가합니다.
// 이 과정을 반복하며 가장 마지막의 돌의 무게를 출력하세요.
// 입출력 예시
// 입력: 2, 7, 4, 1, 8, 1
// 출력: 1
// 입력: 5, 3, 5, 3, 4
// 출력: 2
import java.util.PriorityQueue;
public class Practice2 {
public static void solution(int[] stones) {
PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
for(int stone: stones) {
pq.offer(stone);
}
// 돌 두개를 꺼내서 비교 후 차이만큼은 다시 추가
while (pq.size() > 1) {
int stone1 = pq.poll();
int stone2 = pq.poll();
int diff = Math.abs(stone1 - stone2);
if (diff != 0) {
pq.offer(diff);
}
}
System.out.println(pq.poll());
}
public static void main(String[] args) {
// Test code
int[] stones = {2, 7, 4, 1, 8, 1};
solution(stones);
stones = new int[]{5, 3, 5, 3, 4};
solution(stones);
}
}
1
2
nums 배열에 주어진 정수들 중에서 가장 많이 발생한 숫자들 순으로 k 번째 까지 출력
// Practice3
// nums 배열에 주어진 정수들 중에서 가장 많이 발생한 숫자들 순으로 k 번째 까지 출력하세요.
// 빈도가 같은 경우에는 값이 작은 숫자가 먼저 출력되도록 구현하세요.
// 입출력 예시
// 입력: 1, 1, 1, 2, 2, 3
// k: 2
// 출력: 1, 2
// 입력: 3, 1, 5, 5, 3, 3, 1, 2, 2, 1, 3
// k: 3
// 출력: 3, 1, 2
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class Practice3 {
public static void solution1(int[] nums, int k) {
// 값 별 빈도 수 기록
HashMap<Integer, Integer> map = new HashMap<>();
for(int num: nums){
map.put(num, map.getOrDefault(num,0) + 1);
}
// 빈도가 같은 경우는 key 기준으로 정렬, 다른 경우는 빈도 수 기준으로 정렬
//키 기준으로는 오름차순, 빈도수 기준으로는 내림차순.
PriorityQueue<Map.Entry<Integer, Integer>> pq =
new PriorityQueue<>((x, y) -> y.getValue() == x.getValue() ?
x.getKey() - y.getKey() : y.getValue() - x.getValue());
for(Map.Entry<Integer, Integer> item: map.entrySet()){
pq.add(item);
}
// k 번째 전까지 꺼낸 후 출력
for (int i = 0; i < k; i++) {
Map.Entry<Integer, Integer> cur = pq.poll();
System.out.print(cur.getKey() + " ");
}
System.out.println();
}
// solution2
class Num implements Comparable<Num> {
int key;
int freq;
public Num(int key, int freq) {
this.key = key;
this.freq = freq;
}
@Override
public int compareTo(Num o) {
if (this.freq == o.freq) {
return this.key - o.key;
} else {
return o.freq - this.freq;
}
}
}
public static void solution2(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<>();
for(int num: nums){
map.put(num, map.getOrDefault(num,0) + 1);
}
PriorityQueue<Num> pq = new PriorityQueue<>();
for(Map.Entry<Integer, Integer> item: map.entrySet()){
pq.add(new Practice3().new Num(item.getKey(), item.getValue()));
}
for (int i = 0; i < k; i++) {
Num cur = pq.poll();
System.out.print(cur.key + " ");
}
System.out.println();
}
public static void main(String[] args) {
// Test code
int[] nums = {1, 1, 1, 2, 2, 3};
solution1(nums, 2);
solution2(nums, 2);
System.out.println();
nums = new int[]{3, 1, 4, 4, 3, 3, 1, 2, 2, 1, 3};
solution1(nums, 3);
solution2(nums, 3);
}
}
1 2
1 2
3 1 2
3 1 2
문자열 s 가 주어졌을 때, 문자열 내에 동일한 알파벳이 연속적으로 배치되지 않도록 재배치
// Practice4
// 문자열 s 가 주어졌을 때, 문자열 내에 동일한 알파벳이 연속적으로 배치되지 않도록 재배치 하세요.
// 재배치가 가능한 경우 재정렬한 문자열을 반환하고 불가능한 경우 null 을 반환하세요.
// 입출력 예시
// 입력: "aabb"
// 출력: "abab"
// 입력: "aaca"
// 출력: null
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
public class Practice4 {
public static String solution(String s) {
// 알파벳 별 빈도수 기록
HashMap<String, Integer> map = new HashMap<>();
for(String item: s.split("")){
map.put(item, map.getOrDefault(item,0) + 1);
}
// 빈도수 기준 maxHeap
PriorityQueue<Map.Entry<String, Integer>> pq =
new PriorityQueue<>((x, y) -> y.getValue() - x.getValue());
for(Map.Entry<String, Integer> item: map.entrySet()){
pq.add(item);
}
// 빈도수가 높은 알파벳부터 나오며,
// 알파벳 하나를 배치하고 그 다음 알파벳을 꺼낸 후 이전의 알파벳 빈도수가 남아있으면 다시 넣어줌
// 이렇게 하면 교차로 알파벳을 배치시킬 수 있음
StringBuffer sb = new StringBuffer();
Map.Entry<String, Integer> prev = null;
while (!pq.isEmpty()) {
Map.Entry<String, Integer> cur = pq.poll();
// 이전 알파벳의 빈도수가 남아있었다면 pq 에 다시 넣어줌
if (prev != null && prev.getValue() > 0) {
pq.offer(prev);
}
// sb 에 알파벳 연결 후 해당 빈도수 감소
sb.append(cur.getKey());
cur.setValue(cur.getValue() - 1);
// 현재 알파벳에 대한 빈도수가 남아 있는데 pq 가 비어있으면,
// 더 이상 교차로 배치시킬 알파벳이 없으므로 null 반환
prev = cur;
if (pq.isEmpty() && prev.getValue() > 0) {
return null;
}
}
return sb.toString();
}
public static void main(String[] args) {
// Test code
System.out.println(solution("aabb"));
System.out.println(solution("aaaaabccd"));
System.out.println(solution("aaca"));
}
}
abab
acadacaba
null
출처 : 제로베이스
Leave a comment