오늘의 학습 키워드
- Kth Largest Element in a Stream
공부한 내용 본인의 언어로 정리하기
class KthLargest {
private PriorityQueue<Integer> minHeap;
private int k;
public KthLargest(int k, int[] nums) {
this.k = k;
minHeap = new PriorityQueue<>(k); //크기가 k이게 만들면 k번째에 있는값이 제일 작은 값이며 뽑아내야 할 값이 된다.
for(int i = 0; i < nums.length; i++){ //nums 배열의 모든 값을 add메서드를 MinHeap에 추가
add(nums[i]);
}
}
//새로운 값을 추가하고(add) k번째로 큰 값을 반환(peek)
public int add(int val) { //add는 항상 k개의 가장 큰 요소를 유지하고, k번째로 큰 요소를 반환한다.
if(minHeap.size() < k){ //minHeap의 size가 k보다 작을 경우 k번째 값을 추출할 수 없기때문에 k개 될때까지 채운다.
minHeap.offer(val);
} else if (val > minHeap.peek()){ //minHeap의 새로운 값이 minHeap의 최소 요소보다 큰 경우
minHeap.poll(); //minHeap의 가장 작은 요소를 제거합니다.
minHeap.offer(val); //새로운 val값을 minHeap에 추가합니다.
}
return minHeap.peek();
}
}오늘의 회고
오늘은 문제 모아보기에서 먼저 문제를 보고 어떻게 풀어야 할지 적고 시작했는데도 55분이 걸렸다.
nums의k번째 배열을 추출하는 메서드를 만들기- 반복문으로
nums.length만큼 반복 add(nums[i])를 추가- 추가가 될때마다
nums의k번째 배열을 가져오기 - 결과 출력
하지만 만들면서도 어떻게 해야할지 몰라서 계속 해매다 문제의 유형인 Heap을 검색하다 PriorityQueue에 대해서 보았고 단어를 보니 Queue에 관한 문법을 알아보면 될 것 같아서 검색을 하였다.
-
PriorityQueue는Queue의 모든 속성을 가지고 있으며MinHeap으로 데이터를 갖고 있으며 오름차순으로poll을 해주는 자료구조이다. -
poll()또는peek()사용할 경우 자료 구조의 가장 작은 데이터를 출력할 수 있다.offer(): 데이터를 집어넣는다.poll(): 가장 작은 데이터를 제거한다.peek(): 가장 작은 데이터를 뽑는다.
가장 작은 데이터를 뽑아낸다면 k번째 배열에 집착하는 것이 아닌 k번째가 가장 작은 데이터이면 되지 않을까? 에서 시작되었다.
그렇다면 Queue의 초기 크기를 k로 설정을 한다면 peek()으로 뽑아내면 k번째 값이 나오겠구나 생각했다.
객체의 모든 메서드에서 접근할 수 있도록 우선 PriorityQueue와 변수 k를 클래스 변수로 선언을 해주었다.
private PriorityQueue<Integer> minHeap;
private int k;이후 예시와 같이 add(val)값을 추가해주기 위해서 nums.length 만큼 add(nums[i])를 해주었다.
public KthLargest(int k, int[] nums) {
this.k = k;
//크기가 k이게 만들면 k번째에 있는값이 제일 작은 값이며 뽑아내야 할 값이 된다.
minHeap = new PriorityQueue<>(k);
//nums 배열의 모든 값을 add메서드를 사용해 minHeap에 추가
for(int i = 0; i < nums.length; i++){
add(nums[i]);
}
}이제 모든 값을 minHeap에 추가해 주었으니 add의 내용을 만들어야 했고 k번째 값이 가장 작다가 유효하려면 가져야하는 조건들을 생각했다.
minHeap의 사이즈가k보다 작으면k번째의 값이 제일 작다는 것이 성립이 되지 않음
(k=5일때 사이즈가 3 이라면 5번째의 값이 아닌 3번째의 값이 뽑혀져 나온다는 것)- 새로 추가 되는
val값이minHeap의 최소값 보다 크다면 확장이 되어 크기가 커지므로 성립되지 않는다.
(k가 3 일때minHeap의 최소값이 3 인데val값이 5 라면, 이미 최소값 앞에 추가되어 버려 3번째가 아닌 4번째의 값이 최소값이 되어버린다는 것)
1번의 경우 minHeap의 사이즈가 k보다 작으면 사이즈가 k가 될때 까지 추가를 하면 된다.
2번의 경우에는 새 val의 값이 최소값을 넘어버린다면 미리 가장 작은 요소를 제거한 후 val값을 추가해 주면 해결이 된다.
public int add(int val) { //add는 항상 k개의 가장 큰 요소를 유지하고, k번째로 큰 요소를 반환한다.
if(minHeap.size() < k){ //minHeap의 size가 k보다 작을 경우 k번째 값을 추출할 수 없기때문에 k개 될때까지 채운다.
minHeap.offer(val);
} else if (val > minHeap.peek()){ //minHeap의 새로운 값이 minHeap의 최소 요소보다 큰 경우
minHeap.poll(); //minHeap의 가장 작은 요소를 제거합니다.
minHeap.offer(val); //새로운 val값을 minHeap에 추가합니다.
}
return minHeap.peek();
}이렇게 되면 값이 작거나 많을때 해결이 돼서 결과가 Accepted가 나온다.
AI 코드리뷰
현재 코드 리뷰:
장점:
- 우선순위 큐(
PriorityQueue)를 사용하여k번째로 큰 요소를 효율적으로 관리하고 있습니다. - 클래스 변수를 적절히 사용하여 객체의 상태를 유지하고 있습니다.
- 생성자와
add메서드의 기본 로직이 올바르게 구현되어 있습니다.
개선 가능한 점:
-
예외 처리
k가 0 이하인 경우에 대한 처리가 없습니다. 이는IllegalArgumentException을 발생시켜야 합니다. -
초기화 최적화
생성자에서nums배열의 모든 요소를add메서드를 통해 추가하고 있는데, 이는 비효율적일 수 있습니다.k개 이상의 요소가 있을 때는 정렬 후 상위k개만 추가하는 것이 더 효율적일 수 있습니다. -
add 메서드의 반환 값
minHeap의 크기가k보다 작을 때의 반환 값 처리가 부적절할 수 있습니다. 이 경우null을 반환하거나 특별한 값을 반환하는 것이 더 명확할 수 있습니다. -
주석
주석이 상세하게 작성되어 있어 좋습니다. 하지만 일부 주석은 코드 자체로 명확할 수 있으므로, 더 간결하게 만들 수 있습니다.
개선된 코드 제안
class KthLargest {
private final PriorityQueue<Integer> minHeap;
private final int k;
public KthLargest(int k, int[] nums) {
if (k <= 0) {
//예외 처리
throw new IllegalArgumentException("k must be greater than 0");
}
this.k = k;
this.minHeap = new PriorityQueue<>(k);
// 최적화된 초기화
Arrays.sort(nums);
for (int i = Math.max(0, nums.length - k); i < nums.length; i++) {
minHeap.offer(nums[i]);
}
}
public Integer add(int val) {
if (minHeap.size() < k) {
minHeap.offer(val);
return minHeap.size() == k ? minHeap.peek() : null;
}
if (val > minHeap.peek()) {
minHeap.poll();
minHeap.offer(val);
}
return minHeap.peek();
}
}개선된 버전의 장점:
k에 대한 유효성 검사를 추가했습니다.- 초기화 과정을 최적화했습니다.
add메서드의 반환 타입을Integer로 변경하여null을 반환할 수 있게 했습니다.- 불필요한 주석을 제거하고 코드를 더 자명하게 만들었습니다.
이러한 변경으로 코드의 견고성과 효율성이 향상될 것입니다.
시간 복잡도 개선한 코드
import java.util.PriorityQueue;
import java.util.Random;
class KthLargest {
private final PriorityQueue<Integer> minHeap;
private final int k;
public KthLargest(int k, int[] nums) {
if (k <= 0) {
throw new IllegalArgumentException("k must be greater than 0");
}
this.k = k;
this.minHeap = new PriorityQueue<>(k);
// QuickSelect를 사용하여 k번째로 큰 요소 찾기
if (nums.length > 0) {
int kthLargest = quickSelect(nums, 0, nums.length - 1, nums.length - k);
// k개의 가장 큰 요소만 힙에 추가
for (int num : nums) {
if (num >= kthLargest) {
add(num);
}
}
}
}
public Integer add(int val) {
if (minHeap.size() < k) {
minHeap.offer(val);
} else if (val > minHeap.peek()) {
minHeap.poll();
minHeap.offer(val);
}
return minHeap.size() == k ? minHeap.peek() : null;
}
private int quickSelect(int[] nums, int left, int right, int k) {
if (left == right) return nums[left];
int pivotIndex = new Random().nextInt(right - left + 1) + left;
pivotIndex = partition(nums, left, right, pivotIndex);
if (k == pivotIndex) {
return nums[k];
} else if (k < pivotIndex) {
return quickSelect(nums, left, pivotIndex - 1, k);
} else {
return quickSelect(nums, pivotIndex + 1, right, k);
}
}
private int partition(int[] nums, int left, int right, int pivotIndex) {
int pivot = nums[pivotIndex];
swap(nums, pivotIndex, right);
int storeIndex = left;
for (int i = left; i < right; i++) {
if (nums[i] < pivot) {
swap(nums, storeIndex, i);
storeIndex++;
}
}
swap(nums, right, storeIndex);
return storeIndex;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}이 개선된 버전의 시간 복잡도:
생성자
1. QuickSelect: 평균 O(n), 최악의 경우 O(n^2)
2. 힙 구성: O(k log k)
3. 전체: 평균 O(n + k log k), 최악의 경우 O(n^2 + k log k)
add 메서드
1. O(log k)
장점 :
1. 초기 배열이 큰 경우 정렬보다 훨씬 효율적입니다.
2. 메모리 사용량이 k로 제한됩니다.
3. add 메서드의 효율성은 유지됩니다.
단점
1. 코드가 더 복잡해집니다.
2. 최악의 경우 QuickSelect가 O(n^2)이 될 수 있지만, 평균적으로는 매우 효율적입니다.
이 구현은 큰 데이터셋에 대해 더 효율적이며, 특히 k가 nums의 크기에 비해 상대적으로 작을 때 큰 이점이 있습니다.
내일 공부할 것 :
PriorityQueue를 사용을 해봤으니 그냥 Queue에 대해서도 알아보고, Heap에 대해서
Java 뿐만 아니라 CS적인 지식도 정리를 해놓아야 겠다.
문제
https://leetcode.com/problems/kth-largest-element-in-a-stream/
