Queue๋ ๋จผ์ ๋ค์ด๊ฐ ๋ฐ์ดํฐ๊ฐ ๋จผ์ ๋์ค๋ ํ์์ด๋, Priority Queue๋ ์ด์ ๋ค๋ฅด๊ฒ ๋ฐ์ดํฐ๋ฅผ ๊บผ๋ผ ๋ ์ฐ์ ์์๊ฐ ๊ฐ์ฅ ๋์ ๊ฒ๋ถํฐ ๋์ค๊ฒ ๋๋ค. ์ผ๋ฐ์ ์ธ ํ์ฒ๋ผ ์ถ๊ฐ/์ญ์ ์ฐ์ฐ์ด ์์ง๋ง, ๊ทธ ์์์ ๊ด๊ณ์์ด ์ฐ์ ์์๋ฅผ ๊ณ ๋ คํ์ฌ ๋ฐ์ดํฐ๋ฅผ ๊ฐ์ ธ์ฌ ์ ์๋ค.
Priority Queue๋ ํ ๊ตฌ์กฐ(ํธ๋ฆฌ๊ตฌ์กฐ)๋ฅผ ์ด์ฉํด์ ๋ง๋ค๊ณ , ํฐ ๊ฐ์ด ์ฐ์ ์ด ๋๋ ์ต๋ํ๊ณผ ์์ ๊ฐ์ด ์ฐ์ ์ด ๋๋ ์ต์ํ์ด ์๋ค๊ณ ์๊ฐํ๋ฉด ๋๋ค. (default = ์ต์ ํ)
๐น๏ธ Priority Queue ์ฌ์ฉ๋ฒ
- ์ต์ ํ (์ต์๊ฐ๋ถํฐ ๋ฐฐ์ด)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
- ์ต๋ ํ (์ต๋๊ฐ๋ถํฐ ๋ฐฐ์ด)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(((o1, o2) -> o2-o1));
๐ ์๋ฃํ ๋์ ๋ด๊ฐ ๋ง๋ class ํํ๋ฅผ ์ฌ์ฉํ๋ฉด
public class Main{
public static class Student implements Comparable<Student> {
String name;
int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "์ด๋ฆ : " + name + ", ๋์ด : " + age;
}
@Override
public int compareTo(Student stud) {
return this.age <= stud.age ? 1 : - 1;
// return this.age-stud.age; // ๊ฒฐ๊ณผ๋ ๋์ด๊ฐ ์ ์ ์๋ถํฐ ์ถ๋ ฅ๋จ
}
}
public static void main(String[] args){
PriorityQueue<Student> pq = new PriorityQueue<Student>();
pq.add(new Student("๊น๊ณ ์ต", 12));
pq.add(new Student("์ด๊ณ ์ต", 15));
}
}
โ๏ธ this.age-stud.age ๋ก ์์ฑํ๋ค๋ฉด ๊ณ์ฐ ๊ฒฐ๊ณผ๊ฐ ์๋ฃํ ๋ฒ์๋ฅผ ๋์ด์์ง ์๋๋ก (OverFlow) ์ฃผ์ํด์ผ ํ๋ค !
Comparable & Comparator ๋?
๊ฐ์ฒด๋ฅผ ๋น๊ตํ ์ ์๊ฒ ํด์ฃผ๋ ์ธํฐํ์ด์ค์ด๋ค.
docs.oracle.com/javase/8/docs/api/java/lang/Comparable.html#method.summary
Comparable ์ธํฐํ์ด์ค์ compareTo(T o) ๋ฉ์๋๊ฐ ์ ์ธ๋์ด์์ด ์ด ๋ฉ์๋๋ฅผ Override ํด์ผํ๋ค.
docs.oracle.com/javase/8/docs/api/java/util/Comparator.html#method.summary
Comparator ์ธํฐํ์ด์ค์ compare(T o1, T o2) ๋ฉ์๋๊ฐ ์ ์ธ๋์ด์๊ณ ์ด ๋ฉ์๋๋ง Overrideํด์ ๊ตฌํํด์ฃผ๋ฉด ๋๋ค.
์ด๋ฌํ ์ธํฐํ์ด์ค๋ฅผ ์ฌ์ฉํ๋ ์ด์ ๋ ํด๋์ค ๊ฐ์ฒด์ ์๋ ๊ฐ๋ค์ ์ฝ๊ฒ ๋น๊ตํ ์ ์๋๋ก ๋ง๋ค๊ธฐ ์ํด์์ด๋ค.
primitive type์ ๋ถ๋ฑํธ๋ก ๊ทธ๋ฅ ๋น๊ต ๊ฐ๋ฅํ๊ฒ ์ง๋ง, ํ๋ฒ๊ณผ ๋์ด ์ ๋ณด๋ฅผ ๊ฐ๊ณ ์๋ ํ์๋ค์ ๋น๊ตํ๋ ๊ฒ์ ์ด๋ค ๊ฒ์ ๊ธฐ์ค์ผ๋ก ์ฐ์ ์์๋ฅผ ๊ฐ๊ฒ ๋๋์ง ์ ์ ์๋ค. ์ด ๋ฌธ์ ์ ์ ํด๊ฒฐํ๊ธฐ ์ํด Comparator ๋๋ Comparable ์ธํฐํ์ด์ค๋ฅผ ์ฌ์ฉํ๋ค.
Comparable& Comparator์ฐจ์ด์
- Comparable : ์๊ธฐ ์์ ๊ณผ ๋งค๊ฐ๋ณ์ ๊ฐ์ฒด๋ฅผ ๋น๊ตํ๋ค.
- Comparator : ๋ ๋งค๊ฐ๋ณ์ ๊ฐ์ฒด๋ฅผ ๋น๊ตํ๋ค.
๐ ๋น๊ต ๋์์ด ๋ค๋ฅด๊ณ , Comparator๋ Comparable๊ณผ ๋ค๋ฅด๊ฒ util ํจํค์ง์ ์์ด import ํด์ค์ผ ํ๋ค.
Comparable
class Student implements Comparable<Student> {
int age; // ๋์ด
int classNumber; // ํ๊ธ
Student(int age, int classNumber) {
this.age = age;
this.classNumber = classNumber;
}
@Override
public int compareTo(Student o) {
// ์๊ธฐ์์ ์ age๊ฐ o์ age๋ณด๋ค ํฌ๋ค๋ฉด ์์
if(this.age > o.age) {
return 1;
}
// ์๊ธฐ ์์ ์ age์ o์ age๊ฐ ๊ฐ๋ค๋ฉด 0
else if(this.age == o.age) {
return 0;
}
// ์๊ธฐ ์์ ์ age๊ฐ o์ age๋ณด๋ค ์๋ค๋ฉด ์์
else {
return -1;
}
/*
* ๋ง์ฝ ์์ ์ age๊ฐ o์ age๋ณด๋ค ํฌ๋ค๋ฉด ์์๊ฐ ๋ฐํ ๋ ๊ฒ์ด๊ณ ,
* ๊ฐ๋ค๋ฉด 0์, ์๋ค๋ฉด ์์๋ฅผ ๋ฐํํ ๊ฒ์ด๋ค.
*/
//return this.age - o.age;
}
}
์๊ธฐ ์์ ๊ณผ ์๋๋ฅผ ๋น๊ตํ๋ค. this๋ ๊ฐ์ฒด ์์ ์ ๋ํ๋ด๊ณ , o๋ ๋ค๋ฅธ ๊ฐ์ฒด๋ฅผ ๋ํ๋ธ๋ค.
Comparator
import java.util.Comparator; // import ํ์
class Student implements Comparator<Student> {
int age; // ๋์ด
int classNumber; // ํ๊ธ
Student(int age, int classNumber) {
this.age = age;
this.classNumber = classNumber;
}
@Override
public int compare(Student o1, Student o2) {
// o1์ ํ๊ธ์ด o2์ ํ๊ธ๋ณด๋ค ํฌ๋ค๋ฉด ์์
if(o1.classNumber > o2.classNumber) {
return 1;
}
// o1์ ํ๊ธ์ด o2์ ํ๊ธ๊ณผ ๊ฐ๋ค๋ฉด 0
else if(o1.classNumber == o2.classNumber) {
return 0;
}
// o1์ ํ๊ธ์ด o2์ ํ๊ธ๋ณด๋ค ์๋ค๋ฉด ์์
else {
return -1;
}
/*
* ๋ง์ฝ o1์ classNumber๊ฐ o2์ classNumber๋ณด๋ค ํฌ๋ค๋ฉด ์์๊ฐ ๋ฐํ ๋ ๊ฒ์ด๊ณ ,
* ๊ฐ๋ค๋ฉด 0์, ์๋ค๋ฉด ์์๋ฅผ ๋ฐํํ ๊ฒ์ด๋ค.
*/
//return o1.classNumber - o2.classNumber;
}
}
์ฐธ๊ณ
https://st-lab.tistory.com/243