힙(Heap)을 활용한 알고리즘 문제풀이

오늘 푼 문제: Smallest Number in Infinite Set

구현 기능

• SmallestInfiniteSet(): 모든 양의 정수를 가진 집합을 초기화합니다.
• int popSmallest(): 집합 중 가장 작은 양의 정수를 제거하고 반환합니다.
• void addBack(int num): 만약 num이 집합에 없다면 해당 집합에 num을 추가합니다.

예제 코드

import java.util.*;

public class SmallestInfiniteSet {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    Set<Integer> set = new HashSet();
    public SmallestInfiniteSet() {
        for (int i = 1; i <= 1000 ;i++) {
            pq.offer(i);
            set.add(i);
        }
    }

    public int popSmallest() {
        int smallest = pq.poll();
        set.remove(smallest);
        return smallest;
    }

    public void addBack(int num) {
        if (!set.contains(num)) {
            pq.offer(num);
            set.add(num);
        }
    }
}

• 힙을 구현한 PriorityQueue를 활용하여 문제를 풀어보았습니다.
• Set과 PriorityQueue를 필드 값으로 가집니다.
• 클래스 초기화 시 set/pq에 1부터 1000까지의 양수를 추가합니다.
• popSmallest() 시 set과 pq에서 해당 값을 제거합니다.
• addBack 시 set에서 해당 숫자가 있는지 확인 후 없을 경우 추가해줍니다.

회고

• 생각해보니 set이 없어도 되는 코드였습니다. pq.contains를 활용하면 됐습니다.
• 하지만 해당 코드로 해보니 실행 시간이 늘었습니다...!
  
• 왜 그런지는 오늘은 너무 피곤한 관계로 내일 확인해보겠습니다...!