[코딩테스트] 프로그래머스 - 항해99클럽 코딩테스트 스터디 19일차 : 최소 힙

해당 글은 항해99 클럽 코딩테스트 스터디에서 진행된 19일차(20241115) 비기너 문제에 대한
TIL(Today I Learned) 내용입니다.

	문제 출처) https://www.acmicpc.net/problem/1927
    

---

문제해결에 활용한 핵심포인트!

문제 상황에서 활용하기에 적합한 구조에 대해 고려하기

• 이 문제에서 핵심적으로 필요했던 것은 다음과 같다.
  -> 만약 입력으로 주어진 x가 자연수라면 배열에 x라는 값을 넣는(추가하는)
  -> 입력으로 주어진 정수 x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거
  
  
• 위의 사항에 대해 수행할 수 있는 함수를 가진 것은 Priority Queue
  -> 각각에 대하여 add(), poll() 활용

더 알아보기

1) "Priority Queue란 무엇인가"

• Queue와 함수가 거의 동일하다.
• 차이는 Queue는 FIFO(선입선출)이라면, Priority Queue는 우선순위가 높은 데이터부터 나간다는 것이다.

2) "우선순위 큐 생성 방법

• 방법1) 기본 구현 : 문제풀이에 활용한 방법

// 오름차순
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

// 내림차순
PriorityQueue<Integer> minHeap = new PriorityQueue<>(Collections.reverseOrder());

- 방법2) Comparable 구현
: Comparable Interface 상속받아서 compareTo 메서드를 구현
: 기준이 되는 것에 대한 항목을 compareTo메서드를 통해 명시한다.

// MyMember 클래스에 대해서 우선순위 지정 필요
PriorityQueue<MyMember> memberQueue = new PriorityQueue<>();

// MyMember 클래스를 Comparable<MyMember> 상속받게 한 다음 compareTo 메서드 구현
class MyMember implements Comparable<MyMember>{
    String name;
    int age;

    public MyMember(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // 기준이 되는 것이 age라는 것을 명시하는 것
    @Override
    public int compareTo(MyMember o) {
        return this.age-o.age;
    }
}

• 방법3) 람다식 이용 : 자바 8 이후부터
  : 기본이 숫자는 오름차순, 문자는 알파벳순
  : m1.age - m2.age 가 음수(결국 m1.age < m2.age)이면 m1이 m2 앞
  : m1.age - m2.age가 양수(결국 m1.age > m2.age)이면 m1이 m2 뒤
  : m1.age - m2.age가 0(결국 m1.age = m2.age)이면 m1, m2 순서 유지

PriorityQueue<MyMember> memberQueue = new PriorityQueue<>((m1,m2)->m1.age-m2.age);

• 방법4)Comparator 이용
  : 자바 8 람다식 이전 기본 방식
  : PriorityQueue 생성시에 매개변수로 Comparator클래스의 compare메서드를 구현하여 우선순위를 지정해 줄 수있다.

PriorityQueue<MyMember> memberQueue = new PriorityQueue<>(new Comparator<MyMember>() {
    @Override
    public int compare(MyMember o1, MyMember o2) {
        return o1.age - o2.age;
    }
});

---

위의 내용은 다음을 참고하였습니다.
https://innovation123.tistory.com/112
https://cdragon.tistory.com/entry/자료구조-Heap-Priority-Queue힙과-우선순위-큐