1. 개요
이 사용방법(예제)에서는 Java를 사용하여 배열에서 가장 큰 k개의 요소 를 찾는 문제에 대한 다양한 솔루션을 구현 합니다. 시간 복잡도를 설명하기 위해 Big-O 표기법을 사용합니다.
2. 무차별 대입 솔루션
이 문제에 대한 무차별 대입 솔루션 은 주어진 배열을 k 번 반복하는 것 입니다. 각 반복 에서 가장 큰 값을 찾습니다 . 그런 다음 배열에서 이 값을 제거하고 출력 List에 넣습니다.
public List findTopK(List input, int k) {
List array = new ArrayList<>(input);
List topKList = new ArrayList<>();
for (int i = 0; i < k; i++) {
int maxIndex = 0;
for (int j = 1; j < array.size(); j++) {
if (array.get(j) > array.get(maxIndex)) {
maxIndex = j;
}
}
topKList.add(array.remove(maxIndex));
}
return topKList;
}주어진 배열의 크기를 n 이라고 가정하면 이 솔루션의 시간 복잡도는 O(n * k) 입니다. 또한 이것은 가장 비효율적인 솔루션입니다.
3. 자바 컬렉션 접근 방식
그러나 이 문제에 대한 보다 효율적인 솔루션이 있습니다. 이 섹션에서는 Java 컬렉션을 사용하여 두 가지를 설명합니다.
3.1. 트리셋
TreeSet 은 Red-Black Tree 데이터 구조 를 백본으로 가지고 있습니다. 결과적으로 이 집합에 값을 넣으면 비용이 O(log n) 입니다. TreeSet 은 정렬된 컬렉션입니다. 따라서 모든 값을 TreeSet에 넣고 그 중 첫 번째 k 를 추출할 수 있습니다.
public List<Integer> findTopK(List<Integer> input, int k) {
Set<Integer> sortedSet = new TreeSet<>(Comparator.reverseOrder());
sortedSet.addAll(input);
return sortedSet.stream().limit(k).collect(Collectors.toList());
}이 솔루션 의 시간 복잡도는 O(n * log n) 입니다. 무엇보다 k ≥ log n 일 때 무차별 대입 방식보다 더 효율적이라고 가정합니다 .
TreeSet 에는 중복 항목이 없다는 것을 기억하는 것이 중요합니다 . 결과적으로 솔루션은 고유한 값이 있는 입력 배열에 대해서만 작동합니다.
3.2. 우선순위 큐
PriorityQueue 는 Java 의 힙 데이터 구조 입니다. 그것의 도움으로 우리는 O(n * log k) 솔루션을 얻을 수 있습니다 . 또한 이것은 이전 솔루션보다 더 빠른 솔루션이 될 것입니다. 명시된 문제로 인해 k 는 항상 배열의 크기보다 작습니다. 따라서 O(n * log k) ≤ O(n * log n)을 의미합니다.
알고리즘 은 주어진 배열을 한 번 반복 합니다. 각 반복에서 힙에 새 요소를 추가합니다. 또한 힙의 크기를 k 보다 작거나 같게 유지합니다 . 따라서 힙에서 추가 요소를 제거하고 새 요소를 추가해야 합니다. 결과적으로 배열을 반복한 후 힙에는 k개의 가장 큰 값 이 포함 됩니다.
public List<Integer> findTopK(List<Integer> input, int k) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>();
input.forEach(number -> {
maxHeap.add(number);
if (maxHeap.size() > k) {
maxHeap.poll();
}
});
List<Integer> topKList = new ArrayList<>(maxHeap);
Collections.reverse(topKList);
return topKList;
}4. 선택 알고리즘
주어진 문제를 해결하는 방법에는 여러 가지가 있습니다. 그리고 이 사용방법(예제)의 범위를 벗어나지만 선형 시간 복잡도를 생성하기 때문에 선택 알고리즘 접근 방식을 사용하는 것이 가장 좋습니다 .
5. 결론
이 사용방법(예제)에서는 배열에서 가장 큰 k개의 요소 를 찾는 몇 가지 솔루션을 설명했습니다 .
