꾸준히 진행하고 있는 민문리 스터디의 이번주 알고리즘 주제는 힙 이었다.
코딩 테스트에서 힙 문제는 우선순위 큐를 활용하는 문제로 자주 등장하는 주제다.
우선순위 큐를 사용하는 코딩테스트 문제 여러개를 풀면서 공부하게 된 내용을 적어본다~! (｡◝‿◜｡)
1. 우선순위 큐(PriorityQueue)란?
- 일반적인 큐 : 먼저 들어간 데이터가 먼저 나가는 구조인 FIFO(First-In, First-Out) 형식의 자료구조
- 우선순위 큐 : 들어가는 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조
자바의 우선순위 큐는 내부적으로 힙(Heap) 자료구조를 사용해 구현되어 있다.
2. PriorityQueue 선언 방법
// 우선순위가 낮은 수가 먼저 나옴, 즉 오름차순
PriorityQueue<Integer> queue = new PriorityQueue<>();
// 우선순위가 높은 수가 먼저 나옴, 즉 내림차순
// Collections.reverseOrder()는 우선순위를 반대로 뒤집어주는 역할
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());사용 예시
import java.util.PriorityQueue; // 우선순위 큐 사용 시
import java.util.Collections; // 우선순위 반대로 원할 시
public class A {
public static void main(String[] args) {
// 큐1 : 낮은 수부터 나옴 (오름차순)
PriorityQueue<Integer> queue1 = new PriorityQueue<>();
// 큐2 : 큰 수부터 나옴 (내림차순)
PriorityQueue<Integer> queue2 = new PriorityQueue<>(Collections.reverseOrder());
queue1.offer(1); // 큐1에 원소 1 추가
queue1.offer(10); // 큐1에 원소 10 추가
queue1.offer(100); // 큐1에 원소 100 추가
queue2.offer(1); // 큐2에 원소 1 추가
queue2.offer(10); // 큐2에 원소 10 추가
queue2.offer(100); // 큐2에 원소 100 추가
System.out.println("<큐1 예상결과 : 낮은 수부터 오름차순으로 나옴>");
while(!queue1.isEmpty()) { // 큐1이 빌 때까지 반복
// queue1의 첫 번째 값을 꺼냄
System.out.println("queue1.poll() = " + queue1.poll());
}
System.out.println("<큐2 예상결과 : 높은 수부터 내림차순으로 나옴>");
while(!queue2.isEmpty()) { // 큐2가 빌 때까지 반복
// queue2의 첫 번째 값을 꺼냄
System.out.println("queue2.poll() = " + queue2.poll());
}
}
}결과
<큐1 예상결과 : 낮은 수부터 오름차순으로 나옴>
queue1.poll() = 1
queue1.poll() = 10
queue1.poll() = 100
<큐2 예상결과 : 높은 수부터 내림차순으로 나옴>
queue1.poll() = 100
queue1.poll() = 10
queue1.poll() = 13. PriorityQueue 기본적인 메서드
add(): 우선순위 큐에 원소를 추가. 큐가 꽉 찬 경우 에러 발생offer(): 우선순위 큐에 원소를 추가. 값 추가 실패 시 false 반환remove(): 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 에러 발생poll(): 우선순위 큐에서 첫 번째 값을 반환하고 제거, 비어있으면 null 반환isEmpty(): 우선순위 큐가 비어있는지 확인. 비어있다면 true, 값이 하나라도 있으면 false 반환clear(): 우선순위 큐를 초기화size(): 우선순위 큐에 포함되어 있는 원소의 수를 반환
4. 우선순위 커스텀하기
코딩테스트를 풀다 보면 이 우선순위를 커스텀하는 부분을 잘 사용할 줄 알아야 한다!
위처럼 일반 정수나 문자열같은 건 기본적으로 정의된 우선순위에 따라서 값이 잘 나온다.
그치만 우선순위를 내 멋대로 커스텀해서 사용할 줄 알아야 한다.
🤔 why? 이차원 배열이나 사용자 정의 객체와 같은건 비교 기준이 없기 때문에 우선순위 큐에 넣으면 우선순위에 따라 정렬하려고 할 때 ClassCastException 에러가 발생한다.
따라서 이러한 데이터를 사용할 때는 정렬 기준을 직접 정의해야 한다.
커스텀 예시
import java.util.PriorityQueue;
import java.util.Comparator;
class Student {
private int id; // 학생 ID
private double grade; // 성적 평균
public Student(int id, double grade) {
this.id = id;
this.grade = grade;
}
public double getGrade() {
return this.grade;
}
@Override
public String toString() {
return "ID : " + this.id + ", grade : " + this.grade;
}
}
// 클래스 객체의 우선순위를 위한 클래스
class StudentComparator implements Comparator<Student> {
@Override
public int compare(Student s1, Student s2) {
return Double.compare(s2.getGrade(), s1.getGrade()); // 내림차순
}
}
public class Main {
public static void main(String[] args) {
// 방법 1 : 클래스 정의
// StudentComparator 클래스에서 비교 기준을 정의하여 사용
PriorityQueue<Student> queue = new PriorityQueue<>(new StudentComparator());
// 방법 2 : 익명 클래스 활용
// 바로 Comparator의 compare 메서드를 오버라이드하여 기준 작성
PriorityQueue<Student> queue = new PriorityQueue<>(new Comparator<Student>() {
@Override
public int compare(Student s1, Student s2) {
return Double.compare(s2.getGrade(), s1.getGrade()); // 내림차순
}
});
// 방법 3 : 람다식 사용 (가장 간단한 방식)
// 람다식을 사용해 compare 메서드를 간결히 작성
PriorityQueue<Student> queue = new PriorityQueue<>((s1, s2) -> Double.compare(s2.getGrade(), s1.getGrade())); // 내림차순
// 학생 객체 추가
queue.offer(new Student(1, 88.5));
queue.offer(new Student(2, 95.2));
queue.offer(new Student(3, 91.3));
System.out.println("<예상 결과: 성적 평균이 높은 순으로 출력>");
while (!queue.isEmpty()) {
System.out.println(queue.poll());
}
}
}결과
<예상 결과: 성적 평균이 높은 순으로 출력>
ID : 2, grade : 95.2
ID : 3, grade : 91.3
ID : 1, grade : 88.5예시 설명
-
Double.compre(d1, d2)메서드는 d1과 d2를 비교하여 다음 값을 반환한다.
0: 두 값이 같음.
1: d1이 d2보다 큼.
-1: d1이 d2보다 작음. -
우선순위 큐는 내부적으로 두 요소를 비교할 때 Comparator.compare() 메서드를 사용한다.
-
compare()메서드는 반환값에 따라 요소의 순서를 결정한다.
1: 순서를 바꿈 → 뒤 요소가 앞에 온다.
-1: 순서를 유지함 → 앞 요소가 그대로 남는다.
0: 순서를 바꾸지 않음.public int compare(Student s1, Student s2) { return Double.compare(s2.getGrade(), s1.getGrade()); // 내림차순 }- 위 코드에서
Double.compare(s2.getGrade(), s1.getGrade())는 s2의 성적이 s1보다 클 경우 1을 반환하여 순서를 바꾼다.
결과적으로 성적이 높은 학생이 먼저 나오도록 내림차순 정렬을 정의한 것이다.
👉 즉, 큰 값이 먼저 오도록 우선순위를 설정한 것!
- 위 코드에서
-
람다식 사용
- 람다식을 사용하게 되면 코드를 간결하게 줄일 수 있다.
PriorityQueue<Student> queue = new PriorityQueue<>((s1, s2) -> Double.compare(s2.getGrade(), s1.getGrade())); // 내림차순
- 람다식을 사용하게 되면 코드를 간결하게 줄일 수 있다.
우선순위 큐가 없었으면 직접 힙을 구현해야 했을 텐데, 생각만 해도 너무 복잡하고 아찔하다. 😅
이렇게 좋은 우선순위 큐를 제공하고 있으니, 제대로 익혀두고 코딩 테스트나 프로젝트에서 잘 써먹어보아야지~
이번에 제대로 공부한 덕분에 우선순위 큐를 내 마음대로 자유롭게 정의해서 잘 활용할 수 있을 것 같다!
