https://leetcode.com/problems/smallest-number-in-infinite-set/submissions/1267509620/
1. 문제 및 접근 방법
오늘은 leetCode 2336 문제 Smallest Number in Infinite Set이다.
문제
모든 양의 정수를 포함하는 집합이 있습니다 [1, 2, 3, 4, 5, ...]
클래스 를 구현합니다 SmallestInfiniteSet.
- SmallestInfiniteSet()모든 양의 정수를 포함하도록 SmallestInfiniteSet 개체를 초기화합니다 .
- int popSmallest() 무한 집합에 포함된 가장 작은 정수를 제거 하고 반환합니다.
- void addBack(int num) 무한 집합에 아직 없는 경우 양의 정수를 num무한 집합에 다시 추가합니다 .
모든 양수를 포함하는 집합이 있고, 메서드들이 들어오는대로 실행하기
pop은 현재 배열 중 가장 작은 것을 제거하고 반환
addBack() 은 들어온 수를 맨 앞에 추가, 삭제도 맨 앞으로
우선순위 큐로 구현하면 될 거 같은데 중복이 허용 안되니 그냥 set으로 하자
순서가 중요하니 treeSet으로 구현하면 되지 않을까 ?
linkedList 와 treeset으로 구현하는 걸 고민해보자 어차피 오름차순 정렬한다면, 트리셋도 좋을듯 ?
1000개라고 하니까 1~1000까지 넣어주면 될듯
입출력 예시)
2. 풀이
public SmallestNumberInfiniteSet() {
set = new TreeSet<>(); // 생성자 호출 시 초기화 및 1000까지 세팅
for (int i = 1; i <= 1000; i++) {
set.add(i);
}
}
public int popSmallest() {
// int min = set.stream()
// .min(Comparator.comparing(x -> x))
// .orElseThrow(NoSuchElementException::new);
int min = set.first();
set.remove(min);
return min;
}
public void addBack(int num) {
set.add(num);
}
접근 방법은 많이 떠올랐지만 뭐가 효율적인 지 잘 모르겠다..
2-1 생성자
TreeSet<Integer> set = new TreeSet<>(); 으로
TreeSet에 first() 함수를 사용하기 위해 TreeSet으로 구현했다.
생성자 호출 시
무한 대를 정수로 넣을 수 없으니.. 문제에서 최대 입력 값인 1,000을 기준으로 set.add() 해줌
2-2 treeSet ?
treeSet은 내부적으로 이진 탐색트리(Red-Black 트리)를 기반으로 하고 있으며
1. 정렬된 순서 유지:
* TreeSet은 원소들을 항상 정렬된 상태로 유지합니다. 기본적으로 오름차순으로 정렬되며, 커스텀 정렬 기준을 제공하려면 Comparator를 사용할 수 있습니다.
2. 중복 원소 허용 안 함:
* Set 인터페이스를 구현하기 때문에 중복된 원소를 허용하지 않습니다. 동일한 원소를 추가하려고 하면 기존의 원소가 유지되고 새로운 원소는 추가되지 않습니다.
3. 빠른 검색, 추가, 삭제:
* 이진 탐색 트리를 사용하기 때문에 검색, 추가, 삭제 연산이 평균적으로 O(log n)의 시간 복잡도를 가집니다.
4. 순차적 접근:
* TreeSet은 Iterator를 통해 원소들을 정렬된 순서대로 순회할 수 있습니다.
정렬된 순서를 오름차순으로 유지하며, 중복 원소를 허용하지 않으며, 빠른 삭제와 추가를 위해 선택했다 !
2-3 popSmallest()
요소의 가장 작은 수를 삭제 후 return 하는 메서드인데,
오름차순으로 정렬된 TreeSet의 first()로 제일 앞의 수를 가져오고 그 수를 삭제해줬다..
여기서 제일 고민했다
first()를 몰라 Set의 첫 요소를 어떻게 가져올까 하다가 linkedList 및 우선순위 큐도 생각해봤는데,,
여러 장점들이 다 있겠지만 따로 중복 제거를 하거나 아님 첫 요소를 탐색하거나 하면 효율이 많이 떨어질 것 같다가 first()를 찾았음
2-4 addBack()
간단하다. 요소를 추가해주고 중복이면 추가하지 않는
그래서 TreeSet이 가장 적합하다
3. 느낀 점
먼저 leetcode를 처음 사용해봤는데, 메서드 별로 이렇게 나뉘나 싶고
하나의 플랫폼에 국한되어서 공부 하는 것 보다 여러 플랫폼 별 인기 항목들을 풀어보고 또 익혀 놔야겠다.
그리고 자료구조마다 정확한 검색,추가,삭제, 정렬의 구조들을 싹 다 외워서 최적의 자료구조를 선택하는 것이
어렵다..
그래서 번개같이 떠오르는 걸로만 하는데 점점 하나씩 머리에 넣어 언젠간 제일 적합한 자료구조를 사용하는 희열을..
유 희 열 !