코딩테스트 준비 - Smallest Number in Infinite Set

다시푸는 코딩 테스트 준비 일지

• 응시 사이트 : LeetCode

• 문제 : Smallest Number in Infinite Set

• 사용언어 : C#

• 난이도 : 중

• 풀이시간 : 35m

• 유형 : 정렬리스트, 클래스 구현, 우선순위 큐, 힙

You have a set which contains all positive integers [1, 2, 3, 4, 5, ...].

Implement the SmallestInfiniteSet class:

• SmallestInfiniteSet() Initializes the SmallestInfiniteSet object to contain all positive integers.

• int popSmallest() Removes and returns the smallest integer contained in the infinite set.

• void addBack(int num) Adds a positive integer num back into the infinite set, if it is not already in the infinite set.

Example 1:

Input
["SmallestInfiniteSet", "addBack", "popSmallest", "popSmallest", "popSmallest", "addBack", "popSmallest", "popSmallest", "popSmallest"]
[[], [2], [], [], [], [1], [], [], []]
Output
[null, null, 1, 2, 3, null, 1, 4, 5]

Explanation
SmallestInfiniteSet smallestInfiniteSet = new SmallestInfiniteSet();
smallestInfiniteSet.addBack(2);    // 2 is already in the set, so no change is made.
smallestInfiniteSet.popSmallest(); // return 1, since 1 is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 2, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 3, and remove it from the set.
smallestInfiniteSet.addBack(1);    // 1 is added back to the set.
smallestInfiniteSet.popSmallest(); // return 1, since 1 was added back to the set and
                                   // is the smallest number, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 4, and remove it from the set.
smallestInfiniteSet.popSmallest(); // return 5, and remove it from the set.

Constraints:

• 1 <= num <= 1000

• At most 1000 calls will be made in total to popSmallest and addBack.

문제 풀이 접근

이 문제는, LeetCode에서만 볼 수 있는 느낌의 유형이다. 아직까지 문제를 많이 풀어보진 않았지만, 이런 클래스 구현에 대한 문제는 LeetCode에서밖에 보지 못했다.

문제를 보고 가장 첫 접근은, 리스트 만들고 서치하려고 했으나, 역시 이 문제에 대한 습득이 아직 덜 됐다고 느꼈다.
분명 최소요소를 찾고 pop하고 하는건 우선순위 큐, 힙, 정렬리스트 쪽으로 생각을 먼저했어야 됐는데, 리스트만 생각나는건 아직 경험이 부족한 것 같다.

어쨌건, 문제를 정렬리스트로 활용하여 풀었고, 크게 어려운 문제는 아니었다.

이 문제의 해결 플로우,
1. 문제의 제약 조건, 1000까지 숫자를 넣기때문에, Addback 에서 미리 있다면 추가하지 않는것이 필요하다.
즉, 정렬리스트에 1000까지 모든 수를 끼워넣은 리스트를 세팅한다.
2. PopSmallList는 단순히 최소 요소를 리턴한다.
3. AddBack 은 있다면 딱히 할 것이 없다. ( 이것 때문에 1번에서 1000까지 세팅하는 것이다. )

정답 작성 코드 (C#)

public class SmallestInfiniteSet {
    
    public SortedSet<int> sortSet;

    public SmallestInfiniteSet() {
        sortSet = new SortedSet<int>();
        
        for(int i = 1; i <= 1000; ++i)
            sortSet.Add(i);
        
    }
    
    public int PopSmallest() {
        
        var ret = -1;
        
        if(sortSet.Count > 0)
        {
            ret = sortSet.Min;
            sortSet.Remove(sortSet.Min);
        }
            
        return ret;
    }
    
    public void AddBack(int num) {
        if(sortSet.Contains(num) == true)
            return;
        
        sortSet.Add(num);
    }
}

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

코드 결과