99클럽 코테 스터디 6일차 TIL + Set(Smallest Number in Infinite Set)

오늘의 과제

리트코드 Midium으로 분류된 Smallest Number in Infinite Set 입니다.

 

프로그래머스처럼 자료구조에 대한 분류는 안되어 있지만 문제 자체에 Set이라는 단어가 있으니

주제를 Set으로 분류하였습니다.

문제

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

 

문제는 SmallestInfiniteSet이라는 Class의 세 함수를 구현하면 됩니다.

• 생성자 함수이며 호출시 모든 양의 정수를 포함하여 초기화됩니다.
• infinitSet 안의 가장 작은 정수를 반환하고 해당 정수를 삭제합니다.
• infinitSet 안에 해당 정수가 없다면 추가합니다.

 

무한이라는 말에 어떻게 초기화 해야하나 조금 당황하긴 했으나 입력 제한이 1000 이하로 주어집니다.

 

첫 번째 Solve는 다음과 같이 Set을 이용하여 풀이했습니다.

 

• 생성자 함수 호출시 1부터 1000까지의 정수를 add
• Collections의 min API를 활용하여 최솟값 return 후 remove
• Set은 자료구조 특성상 알아서 중복을 걸러주니 그냥 add

 

코드와 실행 결과는 다음과 같습니다.

import java.util.*;

class SmallestInfiniteSet {

    HashSet<Integer> set;

    public SmallestInfiniteSet() {
        set = new HashSet<Integer>();
        for (int i = 1; i <= 1000; i++) set.add(i);
    }
    
    public int popSmallest() {
        int smallestNum = Collections.min(set);
        set.remove(smallestNum);
        return smallestNum;
    }
    
    public void addBack(int num) {
        set.add(num);
    }
}

 

 

Accepted가 뜨긴 했으나 실행 시간이 뒤에서 상위 5%네요.

 

더 나은 풀이를 위해 작성한 코드에서 개선할 수 있는 부분을 찾아보았습니다.

 

첫 번째는 생성자 메서드입니다.

public SmallestInfiniteSet() {
        set = new HashSet<Integer>();
        for (int i = 1; i <= 1000; i++) set.add(i);
    }

 

1,000이라는 작은 입력 제한으로 상관은 없지만 문제의 조건처럼 Infinite 하지 않습니다.

 

 

두 번째는 최소값 반환 메서드입니다.

public int popSmallest() {
        int smallestNum = Collections.min(set);
        set.remove(smallestNum);
        return smallestNum;
    }

 

 

매번 Collections.min을 통해 최소값을 찾아 제거 후 반환하고 있는데 해당 API를 들어가보면 다음과 같이 동작합니다.

 

 

set 내부를 iterator 객체로 모두 비교하는 로직으로 매번 입력 조건인 N만큼 반복할 수 밖에 없습니다.

 

값을 추가하는 메서드는 문제가 되어 보이지 않아 따로 개선점은 못찾았습니다.

 

 

 

문제의 유형처럼 Set을 활용하여 끝까지 풀고 싶었으나 평소에 다루지 않는 자료구조라 그런지

더 나은 솔루션을 찾지는 못했습니다.

 

조금 헤매다 다른 사람의 풀이를 보고 이해 및 적용해보았습니다.

 

• 생성자 함수 호출시 우선순위 큐 객체 생성
• 큐가 비어있다면 Idx를 반환하고, 비어있지 않다면 큐에서 꺼내서 반환한다.
• 추가할 값이 Idx보다 크다면 무시하고, Idx보다 작다면 해당 값이 최소값이 되니 큐에 넣어준다.

 

풀이 핵심을 간단히 설명해보겠습니다.

 

초기화

최소 값을 추적할 변수 Idx를 1로 셋팅한다.

 

값 추가

Idx보다 큰 값이라면 언젠가 Idx가 반환할테니 무시하고, Idx보다 작은 값일 때만 큐에 넣어준다.

 

최소값 반환

Idx보다 작은 값들의 집한인 큐의 사이즈를 확인하고, 비어있다면 Idx를, 비어있지 않다면 큐에서 꺼내 반환한다.

 

 

두 번째 풀이 코드입니다.

import java.util.*;

class SmallestInfiniteSet {
    private PriorityQueue<Integer> Q;
    private int i = 1;

    public SmallestInfiniteSet() {
        Q = new PriorityQueue<>();
    }
    
    public int popSmallest() {
        if(Q.size() == 0) return i++;
        return Q.poll();
    }
    
    public void addBack(int num) {
        if(num < i && !Q.contains(num)) Q.add(num);
    }
}

 

 

매번 최소 값을 찾는 로직이 사라졌으니 성능이 약 50배는 개선되었네요.

 

 

배운 점

 

첫 번째로 Set을 통한 성능 개선을 이루어 내지 못한 점이 아쉽고

두 번째로는 어제 문제와 비슷하게 풀어낼 수 있었는데 다른 사람의 풀이를 보고 우선순위 큐를

떠올린게 너무 아쉽습니다.

 

하지만 왠지 조금 더 다양하고 많은 문제를 풀 수록 조금은 정형화 된 풀이 방법이 정해질 것 같습니다.

 

6일차까지 진행한 상황에서 정형화된 풀이 방법은 대략 아래와 같은 것 같습니다.

 

짝을 찾는다 => 스택

순서대로 처리한다 => 큐

무작위 값이 추가되지만 매번 최소 값 혹은 최대 값을 리턴한다 => 우선순위 큐

 

문제가 계속 진행될수록 분명 코딩 테스트 단골 문제인 DFS와 BFS가 등장할 것 같은데

과거 기억을 되살릴 수 있을지 모르겠네요.

 

 

오늘의 한줄평

코테는 다양한 유형의 문제를 접해본 놈이 무조건 유리하다.