문제 출처
https://leetcode.com/problems/smallest-number-in-infinite-set/ (리트코드)
학습 키워드
힙(HEAP)
시도 방법
우선순위큐를 활용해 문제 풀이 (성공)
내가 작성한 코드
import java.util.PriorityQueue;
class SmallestInfiniteSet {
PriorityQueue<Integer> priority ;
public SmallestInfiniteSet() {
this.priority = new PriorityQueue<Integer>();
for(int i = 1 ; i<= 1000; i++) {
this.priority.offer(i); //1~1000까지 데이터 등록
}
}
public int popSmallest() {
return this.priority.poll();
}
public void addBack(int num) {
//contains 로 기존재 여부를 확인할 수 있구나
if(!this.priority.contains(num)) this.priority.offer(num);
}
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet obj = new SmallestInfiniteSet();
* int param_1 = obj.popSmallest();
* obj.addBack(num);
*/코드설명
(1) 이 문제는 제약조건이 addBack할 데이터의 범위가 1~1000 이다.
그래서 무한데이터라고는 하지만 최대 1000까지 가지고 있는 우선순위큐를 만들었다.
(2) 많아야 popSmallest , addBack을 1000번 수행하므로 큐가 비어서 에러가 나는 경우는 없기에 popSmallest에서 isEmpty 조건을 추가하지 않고 바로 poll() 메서드를 실행했다.
- poll() 메서드는 큐에서 가장 처음에 위치한 데이터를 추출해 출력한다.
- offer()는 큐 마지막에 데이터를 추가한다.
(3) contains 메서드를 이용해 큐 안에 데이터가 없으면 해당 데이터를 addBack 한다.
실행결과
새롭게 알게된 점
(1) 힙을 이용한 우선순위 큐 메서드 중에 contains() 메서드의 기능을 추가로 배울수 있었다.
(2) 힙에 데이터를 추가할때 add() 와 offer() 이 있다.
이 둘의 차이는 예외를 처리할지 말지 이다.
-
add() : 요소를 반드시 추가해야하며 안그러면 예외가 발생하도록 할 수 있음 (IllegalStateException)
-
offer() : 요소 추가가 실패할 경우 예외 보다는 false 값을 반환하므로 true/false 로 요소 추가 여부를 확인할 수 있음
다음에 풀어볼 문제 - 가장 큰 수
#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL
Backend Developer (Financial)