(24.10.11)
우선 문제를 파악해보자. 문제가 좀 객체지향적이다.
SmallestInfiniteSet()은 모든 양의정수를 가지고 있는 객체이다. int popSmallest()는 가장 작은 양의 정수를 infinite set에서 리턴한다. addBack은 양의 정수를 set에 존재하지 않을 경우에만 infinite set에 넣는다.
위 로직을 클래스로 구현하면 되는 것이다. 초기 코드이다.
class SmallestInfiniteSet {
PriorityQueue<Integer> queue;
public SmallestInfiniteSet() {
queue=new PriorityQueue<Integer>();
for(int i=1; i<1000; i++){
queue.add(i);
}
}
public int popSmallest() {
return queue.remove();
}
public void addBack(int num) {
if(!queue.contains(num))
queue.add(num);
}
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet obj = new SmallestInfiniteSet();
* int param_1 = obj.popSmallest();
* obj.addBack(num);
*/
어떻게 해야 무한대의 양의 정수 Priority Queue를 구현할 수 있을까? 그냥 add는 어차피 존재하지 않을때만 수행하니까 pop PQ를 만들고 popSmallest()함수는 pop PQ에 없는 값 중 가장 작은 값을, addBack()함수는 pop PQ에 있다면 그 값을 없애주면 되지 않을까?
class SmallestInfiniteSet {
PriorityQueue<Integer> queue;
public SmallestInfiniteSet() {
queue=new PriorityQueue<Integer>();
for(int i=1; i<1000; i++){
queue.add(i);
}
}
public int popSmallest() {
if(queue.isEmpty()){
queue.add(1);
return 1;
} else if(queue.peek()==1){
int prev_num=0;
for(int num: queue){
if(prev_num+1!=num) {//연속적이지 않은 최솟값을 발견했다면
queue.add(prev_num+1);
return prev_num+1;
}
prev_num=num;
}
} else {
queue.add(1);
return 1;
}
return -1;
}
public void addBack(int num) {
if(queue.contains(num))
queue.remove(num);
}
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet obj = new SmallestInfiniteSet();
* int param_1 = obj.popSmallest();
* obj.addBack(num);
*/아무것도 통과하지 못했다. 다만 접근법은 마음에 든다.
(24.10.14)
Case 1번을 해결하기 위해 IntelliJ에서 케이스틑 만들어 여러 시도를 해보았다.
다만 기존에 사용하던 방법인 사용하지 못하는(이미 pop한) 값을 저장하는 queue를 순회하는 방법은 이전에 pop한 값과 현재의 pop한 값과의 비교가 필요했다. 이 때 원활한 루프(prev가 나오는 순간 시작과 끝값이 하나 더 필요해지기 때문에)를 위해 방법을 바꾸어 시도하였다.
min값을 1로설정하고 +1한 값들을 queue와 비교하여 없는 값을 리턴하게 바꾸었다.
public int popSmallest() {
int min=1;
if(!queue.contains(min)){//가용한 값이라면
queue.add(min);
return min;
} else {//가용하지 않은 값이라면
while(queue.contains(++min)){}//가용한 값이 나올때까지++
queue.add(min);
return min;
}
}
테스트 케이스 1번은 통과할 수 있었다. 제출결과
48번 테스트케이스까지 진행할 수 있었다.
TLE가 발생한 48번 테스트케이스는 pop만 수행하는 케이스로 현재 내 코드는 가용한 값이 나올 때 까지 while문을 사용해 매번 탐색하기 때문에 n번의 pop이 있다면 n*n O(n^2)의 시간복잡도가 수행된다. 이를 최적화하기 위해 가용한 값을 수시로 업데이트 하도록 하자.
class SmallestInfiniteSet {
PriorityQueue<Integer> queue;
int min_val=1;
public SmallestInfiniteSet() {
queue=new PriorityQueue<Integer>();
}
public int popSmallest() {
int min=min_val;
if(!queue.contains(min)){//가용한 값이라면
queue.add(min);
min_val=findNextMin(min);
return min;
} else {//가용하지 않은 값이라면
return -1;
}
}
private int findNextMin(int min){
while(queue.contains(++min)){}
return min;
}
public void addBack(int num) {
if(queue.contains(num))
queue.remove(num);
if(min_val>num)
min_val=num;
}
}
/**
* Your SmallestInfiniteSet object will be instantiated and called as such:
* SmallestInfiniteSet obj = new SmallestInfiniteSet();
* int param_1 = obj.popSmallest();
* obj.addBack(num);
*/min_val을 두어 바뀌는 경우에만 while루프를 돌게했다(findNextMin함수를 통해). 그 결과
통과는 할 수 있었지만 비교적 낮은 효율성을 보였다.
문제의 원인은 불필요한 PriorityQueue의 사용으로 보아 이를 boolean[]으로 리팩토링하였다.
