- 우선 순위가 높은 데이터가 먼저나옴(FIFO X)
- 모든 데이터에 우선순위가 있음
- Dequeue 시, 우선순위가 높은 순으로 나감
- 우선 순위가 같은 경우는 FIFO
※ enqueue, dequeue : 최소 힙과 최대 힙의 삽입, 삭제와 같음
□ 구현 방법
- 배열
- 연결리스트
- 힙 : 평균을 내보면 제일 빠르므로 자바에서 내부적으로 사용
□ 연결리스트로 우선순위 큐 구현
// 값이 적을수록 우선순위가 높으므로
// 기존 데이터 대비 값이 작으면 앞쪽에 추가
// 정렬된 list라고 생각
public static void enqueue(LinkedList<Integer> list, int data) {
int idx = list.size(); // list의 가장 끝 index 받아옴
for(int i = 0; i< list.size(); i++) {
if(list.get(i) > data) { // 지금 들어온 data가 앞쪽에 위치해야함
idx = i; // 들어갈 위치 저장
break;
}
}
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;
}
□ 자바에서 제공하는 PriorityQueue 사용
// 우선순위 : 기본으로 낮은 숫자 순
PriorityQueue<Integer> pq = new PriorityQueue<>();
// 우선순위 : 높은 숫자 순
PriorityQueue<Integer> pq2 = new PriorityQueue<>(Collections.reverseOrder());
pq.add(5);
pq.add(7);
pq.add(3);
pq.add(1);
System.out.println(Arrays.toString(pq.toArray()));
❖ 나이 순으로 오름차순 또는 내림차순 출력
// 방법 1 : implements를 사용하지 않으면
// 어떤 기준으로 정렬을 할 것인지알 수 없으므로 에러발생
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가 더 작을 때 -1이므로 변경
// 내림차순으로 만들고 싶으면 -1 : 1 (큰 값이 위로 올라감, 내림차순)
return this.age >= o.age ? 1 : -1;
}
Main
// 방법 1
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]));
}
while(!pq.isEmpty()) {
Person p = pq.poll();
System.out.println(p.name + " " + p.age);
}
}
// 방법 2
// 인터페이스 상속 없이 사용하는 방법은 객체를 생성할 때
// 비교조건을 인자에 넘겨줌 (람다식 사용)
PriorityQueue<Person> pq2 = new PriorityQueue<>( // 내림차순 -1 : 1
(Person p1, Person p2) -> p1.age >= p2.age ? 1 : -1);
for
pq2.offer(new Person(name[i], age[i]));
while(!pq2.isEmpty()) {
Person p = pq2.poll();
System.out.println(p.name + " " + p.age);
}
❖ 문자열 사전식 오름차순 (이름순)
public static void solution(String[] name, int[] age) { // 내림차순 p2.name.compareTo(p1.name)
PriorityQueue<Person> pq = new PriorityQueue<>((Person p1, Person p2) -> p1.name.compareTo(p2.name));
for(int i = 0; i< name.length; i++) {
pq.offer(new Person(name[i], age[i]));
}
while(!pq.isEmpty()) {
Person p = pq.poll();
System.out.println(p.name + " " + p.age);
}
}
compareTo
value가 0이 리턴되면 두 string은 같다는 의미이다. 0보다 작은 값이 리턴되면 해당 문자열은 사전식 순으로 argument에 있는 String보다는 작다는 의미이다. 사전식으로 크다 작다 의미는 A가 B보다 작다고 생각하면된다. 0보다 큰 값이 리턴되면 비교되는 문자열이 더 크다는 뜻이다. 그래서 아까 implement에서 따로 오버라이딩을 해준 내용이 이거때문이라고 보면된다.
❖배열에 주어진 정수들 중에서 k번째로 큰 수를 반환하는 프로그램
// 입력 : 3, 1, 2, 7, 6, 4
// k : 2
// 출력 : 6
// minHeap으로 푼것
public static Integer solution(int[] nums, int k) {
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];
}
❖ 우선순위큐로 계산
// 해당 배열로부터 무게가 가장 많이 나가는 돌 두개를 꺼내 충돌
// 무게가 같으면 둘다 소멸, 다르면 남은 무게만큼의 돌을 다시 추가
// 이 과정을 반복하여 가장 마지막 돌의 무게를 출력
// 입력 : 2, 7, 4, 1, 8, 1
// 출력 : 1
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());
}
❖ 빈도 수
// num 배열에 주어진 점수들 중에서 가장 많이 발생한 숫자들 순으로 k번째까지 출력
// 빈도가 같은 경우에는 값이 작은 숫자가 먼저 출력되도록 구현
// 입력 : 3, 1, 5, 5, 3, 3, 1, 2, 2, 1, 3
// k : 3
// 출력 : 3, 1, 2
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); // getOrDefault : 키에 해당하는 값이 있으면 그 값을 가져오고
// 없으면 디폴트 값으로 설정한 0을 가져옴
}
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);
}
for(int i = 0; i<k; i++) {
Map.Entry<Integer, Integer> cur = pq.poll();
System.out.println(cur.getKey() + " ");
}
System.out.println();
}
//
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;
}
}
}
// 1의 PriorityQueue를 클래스로 별도로 작성해서 규칙을 넣어서 쓰는 방법
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 App().new Num(item.getKey(), item.getValue()));
}
for(int i = 0; i<k; i++) {
Num cur = pq.poll();
System.out.println(cur.key + " ");
}
System.out.println();
}
❖ 교차로 문자 배치
// 문자열 s가 주어졌을 때, 문자열 내에 동일한 알파벳이 연속적으로 배치되지 않도록 재배치하시오
// 재배치가 가능한 경우 재정렬한 문자열을 반환하고 불가능한 경우 null을 반환
// 입력 : "aabb" "aaca"
// 출력 : "abab" null
// 문자들의 개수를 센 후에 그 사이에 문자들을 넣을 수 있다면?
// 우선순위 큐에 개수대로 넣고 하나씩 배치하고 다시 큐에 넣기
public static String solution(String s) {
HashMap<String,Integer> hashMap = new HashMap<>();
for(String item : s.split("")) {
hashMap.put(item, hashMap.getOrDefault(item, 0)+1);
}
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>((x, y) -> y.getValue() - x.getValue());
for(Map.Entry<String,Integer> item : hashMap.entrySet()) {
pq.offer(item);
}
StringBuffer sb = new StringBuffer();
Map.Entry<String, Integer> prev = null;
while(!pq.isEmpty()) {
Map.Entry<String, Integer> cur = pq.poll();
if(prev != null && prev.getValue() > 0) { // 이전 데이터의 빈도수가 남아있다면 다시 넣기
pq.offer(prev);
}
sb.append(cur.getKey());
cur.setValue(cur.getValue()-1);
prev = cur;
if(pq.isEmpty() && prev.getValue() > 0) { // 이전데이터가 남아있는데 다음 데이터가 없어
// 교차로 배치할 수 없는 상태
return null;
}
}
return sb.toString();
}
