[코테연습] smallest-number-in-infinite-set

오늘은 leetcode 사이트에서 제공해주는 문제를 풀었다.

 

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

 

leetcode 에 대해서 처음 들어봐서 관련 정보를 찾아보았다.

 

우리나라에서 유명한 프로그래머스, 백준과 마찬가지로 글로벌한 IT 코딩 문제를 제공해주는 사이트 같다.

덕분에 좋은 사이트를 알게 되었다.

 

전체적으로 문제 구성은 심플했다.

 

Set 배열 [1,2,3,4, ..., 1000] 에서

popSmallest() 함수를 사용하면 배열에서 가장 낮은 수를 출력하고,

addBack()함수를 사용하면 배열에 숫자를 입력하는 것이다.

주요 키포인트는 popSmallest 함수를 사용했을 때, 언제 사용하던지 그 배열에서 가장 낮을 수를 출력해야하는 것이다.

 

나는 해당 문제를 저번 문제와 마찬가지로 '우선순위 큐' 를 사용해서 풀었다.

java 에서 제공해주는 PriorityQueue 를 사용하면 리스트에 어떤 숫자를 넣든

poll() 을 사용했을 때 리턴되는 값은 sorting 한 가장 낮은 숫자일 것이다. 

 

2336. Smallest Number in Infinite Set

 

문제에 대한 나의 답은 다음과 같다.

 

 

class SmallestInfiniteSet {

    private static PriorityQueue<Integer> pQueue = null;

    public SmallestInfiniteSet() {

        pQueue = new PriorityQueue<>((o1, o2) -> o1-o2);

        for(int i = 1; i <= 1000; i++) {

            pQueue.offer(i);

        }

    }

   

    public int popSmallest() {

        if(!pQueue.isEmpty()) {

            return pQueue.poll();

        }

        return 0;

    }

   

    public void addBack(int num) {

        if (!pQueue.contains(num)) {

            pQueue.offer(num);

        }

    }

}

 

 

SmallestInfiniteSet() 으로 class 를 초기화 해줄 때, PriorityQueue 를 오름차순으로 선언하였으며, 1부터 1000까지의 숫자를 입력하였다.

 

이후 popSmallest() 함수에서는 pQueue.poll() 값이, addBack() 함수에서는 pQueue 에 해당 숫자가 없다면 offer 해주었다.

answer 된 답에 대한 수치는 다음 이미지와 같다.

 

 

 

 

해당 방법으로 사용한다면, Runtime ms 가 68ms 로 출력되어 꽤나 느린 속도로 수행되는 것을 알 수 있다.

내 생각에는 원인은 queue.contains 함수를 사용하여 PriorityQueue 에서 숫자를 넣을지 여부를 계속 확인하기 때문에 인것으로 생각되었다.

 

그래서 해당 문제를 dp 문제를 푸는 것처럼 응용하여 풀어보기로 했다.

 

import java.util.*;

class SmallestInfiniteSet {

 

    private int[] dp = new int[1001];

    private int point;

    public SmallestInfiniteSet() {

       Arrays.fill(dp, 1);

       point = 1;

    }

   

    public int popSmallest() {

        for (int i = point; i <= 1000; i++) {

            if (dp[i] == 1) {

                point = i;

                dp[i] = 0;

                return i;

            }

        }

        return 0;

    }

   

    public void addBack(int num) {

        if (num < point) {

            point = num;

        }

        dp[num]=1;

    }

}

 

point 변수에 popSmllest() 를 수행한 최종 값을 저장해두고, addBack() 함수로 num을 dp[] 배열에 insert 했을때, point 보다 작다면 point 를 옮기고, dp[] 배열을 다시 1로 초기화 하는 방식으로 바꾸어보았다.

 

 

해당 방법으로 문제를 풀어보니 수행 속도가 9ms 로 더 빨라지고 최적화 되었음을 알 수 있다.

애플리케이션을 개발할때, 개발자의 문제 해결에 대한 이해와 코드 품질이 왜 애플리케이션 최적화에 중요한지를 깨닫는 경험을  할 수 있었다.