99클럽 코테 스터디 6일차 TIL + 힙/리트코드 [2336. Smallest Number in Infinite Set] JAVA 풀이

 

 

 

 

 

 

1. 오늘의 학습 키워드

---

리트코드, 릿코드, LeetCode - 영어권에서 사용하는 한국의 백준/프로그래머스와 같은 코딩 문제 사이트. 

힙-우선순위큐, 최소힙/최대힙, 완전이진트리, 빠르게 최소값/최대값을 찾을 수 있다. 

 

 

2. 오늘의 학습 문제 

---

문제

---

https://leetcode.com/problems/smallest-number-in-infinite-set/description/

 

 

 

 

 

SmallestInfiniteSet(): 모든 양의 정수를 포함하도록 SmallestInfiniteSet() 객체를 초기화한다

int popSmallest(): 무한 집합에서 가장 작은 정수를 삭제 및 리턴한다. 

void addBack(int num): 무한 집합에 양수 num이 있지 않다면 추가한다. 

 

제약

1. 1 <= num <= 1000

2. popSmallest와 addBack 함수의 호출 횟수 합은 1000이하다. 

 

코드

---

 

codeimport java.util.*;

class SmallestInfiniteSet {

    private PriorityQueue<Integer> pq; //전역 변수 선언
    public SmallestInfiniteSet() { // 초기화 함수 
        pq= new PriorityQueue <>();//우선순위 큐 힙 초기화 

        for(int i=1;i<=1000;i++){
            pq.offer(i); //1~1000을 힙에 넣어주기 
        }
        
    }
    
    public int popSmallest() { //top 반환 및 제거
        return pq.poll();
    }
    
    public void addBack(int num) { //중복아닌 경우 add
        if(!pq.contains(num))
            pq.add(num);
    }
}

/**
 * Your SmallestInfiniteSet object will be instantiated and called as such:
 * SmallestInfiniteSet obj = new SmallestInfiniteSet();
 * int param_1 = obj.popSmallest();
 * obj.addBack(num);
 */

 

 

최소값을 찾아내는 문제여서 힙을 선택했다.

제약 조건에서 num이 1~1000에 해당하는 양의 정수이며 중복을 판단해야하기에 힙을 선언하고 해당하는 범위의 양의 정수를 채워넣었다. 

힙을 초기화하는 곳은 SmallestInfiniteSet()함수지만, 그 힙을 다른 함수에서도 사용해야하기에 힙을 전역변수 선언했다. 

popSmallest()는 poll() 메서드를 넣었다. 

addBack(in num) 함수에서는 힙에 num이 있는지 contains()메서드로 검사하고 add한다. 이때 contains()메서드는 전체 큐를 순회하기 때문에 복잡도는 O(n)이다. 만약 이 메서드를 사용하지 않고 별도로 함수를 만들어주면 O(log N) 복잡도로 줄일 수 있을 것이다. 

 

 

 

3. 오늘의 회고

---

•  최소값 이야기가 나오면 힙을 고려해야겠다.
• 리트코드는 들어만 보고 사용하는 건 처음이었는데, 정해진 함수를 작성하는 유형은 지금까지 풀어보았던 경우와 다른 방식이라 새로웠고, 문제 접근 및 해결에 도움이 될 것 같아 자주 사용해보려한다.
• 함수의 목적에 맞게 설계하는 것이었는데, 차후 프로젝트나 개발에서도 함수의 목적과 기능을 세분화하여 설계하고 코드를 작성하면 코드 재사용성이 용이해져 객체지향적 설계에 가까워질 것 같다. 함수 설계에 신경을 많이 써야겠다. 
• 릿허브로 리트코드와 깃허브를 연동을 했다!