99클럽 코테 스터디 6일차 TIL [LeetCode] Smallest Number in Infinite Set (Java)

문제

[LeetCode] Smallest Number in Infinite Set

틀린 코드

import java.util.*;

class SmallestInfiniteSet {
    private PriorityQueue<Integer> pq;
    private Set<Integer> hs;

    public SmallestInfiniteSet() {
        pq = new PriorityQueue<>();
        for(int i = 1; i <= 2147483647; i++) {
            pq.add(i);
        }
        hs = new HashSet<>();
    }
    
    public int popSmallest() {
        int x = pq.poll();
        hs.add(x);
        return n;
    }
    
    public void addBack(int num) {
        if(hs.contains(num)) {
            hs.remove(num);
            pq.add(num);
        }
    }
}

틀린 이유

• positive integer를 덱에 모두 저장하는 과정에서 메모리 초과가 발생했다.
• 우선순위 큐가 비어있는 경우에 대한 처리가 없다.

풀이

• 최솟값에 가장 빠르게 접근하기 위해 우선순위 큐를 사용한다.
• now 변수를 활용해서 현재 사용하는 숫자만 관리한다.
• popSmallest 메서드는 큐가 비어 있을 때 now 값을 반환하고, 그렇지 않으면 큐에서 가장 작은 값을 반환한다.
• addBack 메서드는 현재 큐에 존재하지 않으면서, now보다 작은 값을 반환한다.

정답 코드

class SmallestInfiniteSet {
    private PriorityQueue<Integer> pq;
    private int now;

    public SmallestInfiniteSet() {
        pq = new PriorityQueue<>();
        now = 1;
    }
    
    public int popSmallest() {
        if (!pq.isEmpty()) {
            return pq.poll();
        }
        return now++;
    }
    
    public void addBack(int num) {
        if (num < now && !pq.contains(num)) {
            pq.offer(num);
        }
    }
}

다른 풀이

• 배열을 사용한다.
  • num의 범위가 1000 이하인 양의 정수이므로 notAdded는 크기는 1001
• popSmallest 함수에서는 notAdded를 순회해 false인 값을 찾아서 now에 저장하고 반환한다.
• addBack 함수에서는 해당 인덱스의 notAdded 값을 false로 반환하고, num과 now 중 작은 값을 now에 저장한다.

class SmallestInfiniteSet {
	int now;
	boolean[] notAdded;

	public SmallestInfiniteSet() {
		now = 1;
		notAdded = new boolean[1001];
	}

	public int popSmallest() {
		for(int i = now; i < 1001; i++){
			if(!notAdded[i]) {
				now = i;
				notAdded[i] = true;
				break;
			}
		}
		return now;
	}

	public void addBack(int num) {
		notAdded[num] = false;
		now = Math.min(num, now);
	}
}