[99클럽 코테 스터디_ DAY 10] K번째로 큰 요소

yewon·2024년 8월 1일

항해99TIL

스터디

목록 보기

10/22

K번째로 큰 요소

✏️오늘의 문제

💡나의 풀이

class KthLargest {
    ArrayList<Integer> arr = new ArrayList<Integer>();
    int k; // k 값을 저장할 변수

    public KthLargest(int k, int[] nums) {
        this.k = k; // k 값을 클래스 변수에 저장

        // 초기 배열의 값 추가
        for (int num : nums) {
            arr.add(num);
        }
        
        // 정렬
        Collections.sort(arr);
    }

    public int add(int val) {
        arr.add(val);
        Collections.sort(arr);

        int index = arr.size();
        
        // k보다 작은 경우에는 가장 큰 값을 반환
        if (index < k) {
            return arr.get(index - 1); // 현재 가장 큰 값 반환
        }
        
        // k번째로 큰 값을 반환
        return arr.get(index - k);
    }
}

이 코드는 KthLargest라는 클래스를 정의하여, 주어진 정수 배열에서 k번째로 큰 요소를 효율적으로 찾을 수 있는 기능을 제공합니다. 아래는 코드의 주요 구성 요소와 기능에 대한 설명입니다.

클래스 구조

변수 선언
- ArrayList<Integer> arr: 정수를 저장할 리스트로, 입력된 값들을 저장합니다.
- int k: k번째로 큰 값을 찾기 위해 설정된 정수입니다.
생성자
- public KthLargest(int k, int[] nums): 클래스의 생성자로, k와 초기 배열 nums를 매개변수로 받습니다.
  - this.k = k: k 값을 클래스의 변수에 저장합니다.
  - for (int num : nums): 입력 배열의 각 요소를 리스트에 추가합니다.
  - Collections.sort(arr): 리스트를 정렬하여 오름차순으로 만듭니다. 이렇게 하면 k번째로 큰 값을 쉽게 찾을 수 있습니다.
메소드
- public int add(int val): 새로운 값을 리스트에 추가하고 k번째로 큰 값을 반환하는 메소드입니다.
  - arr.add(val): 새로운 값을 리스트에 추가합니다.
  - Collections.sort(arr): 리스트를 다시 정렬하여 새로운 값을 포함합니다.
  - int index = arr.size(): 현재 리스트의 크기를 저장합니다.
  - if (index < k): 리스트의 크기가 k보다 작을 경우, 가장 큰 값을 반환합니다.
  - return arr.get(index - k): k번째로 큰 값을 반환합니다.

작동 원리

클래스를 초기화할 때, 주어진 배열의 요소를 ArrayList에 저장하고 정렬합니다. 이후 add 메소드를 통해 새로운 값을 추가하면, 리스트를 다시 정렬하고 k번째로 큰 값을 손쉽게 찾을 수 있습니다.
이 구현은 k번째로 큰 값을 찾기 위해 리스트를 매번 정렬하므로, 성능상 효율적이지 않을 수 있습니다. 하지만 코드가 간단하고 이해하기 쉬운 장점이 있습니다.

결론

이 KthLargest 클래스는 k번째로 큰 값을 효과적으로 찾는 기능을 제공하며, 간단한 구조 덕분에 이해하기 쉽습니다. 그러나 성능을 개선하기 위해서는 다른 자료구조(예: 우선순위 큐)를 사용하는 방법을 고려할 수 있습니다.

💡다른 사람의 풀이

class KthLargest {

    private static PriorityQueue<Integer> minHeap;
    private static int k = 0;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        minHeap = new PriorityQueue<>();
        for (int i: nums) {
            add(i);
        }
    }
    
    public int add(int val) {
        minHeap.offer(val);
        while (minHeap.size() > k) {
            minHeap.poll();
        }
        return minHeap.peek();
    }
}

클래스 구조

변수 선언
- private static PriorityQueue<Integer> minHeap: 최소 힙(min heap)을 구현하기 위한 우선순위 큐입니다. 이 큐는 k개의 가장 큰 값을 유지합니다.
- private static int k: k번째로 큰 값을 찾기 위한 변수입니다. 이 변수는 클래스의 모든 인스턴스에서 공유됩니다.
생성자
- public KthLargest(int k, int[] nums): 클래스의 생성자로, k와 초기 배열 nums를 매개변수로 받습니다.
  - this.k = k: k 값을 클래스 변수에 저장합니다.
  - minHeap = new PriorityQueue<>(): 새로운 최소 힙을 생성합니다.
  - for (int i: nums): 입력 배열의 각 요소를 add 메소드를 통해 힙에 추가합니다.
메소드
- public int add(int val): 새로운 값을 힙에 추가하고 k번째로 큰 값을 반환하는 메소드입니다.
  - minHeap.offer(val): 새로운 값을 힙에 추가합니다.
  - while (minHeap.size() > k): 힙의 크기가 k를 초과하면, 가장 작은 값을 제거하여 k개의 가장 큰 값만 유지합니다. 이 과정은 poll() 메소드를 사용하여 수행됩니다.
  - return minHeap.peek(): k번째로 큰 값은 최소 힙의 루트 값이므로, 이를 반환합니다.

작동 원리

KthLargest 클래스의 인스턴스가 생성될 때, 주어진 배열의 요소를 최소 힙에 추가하여 k개의 가장 큰 값을 유지합니다.
add 메소드를 호출하면 새로운 값이 힙에 추가되고, 힙의 크기가 k를 초과할 경우 가장 작은 값이 제거됩니다. 이렇게 하면 항상 k개의 가장 큰 값이 힙에 남게 됩니다.
k번째로 큰 값은 최소 힙의 루트 값으로 쉽게 접근할 수 있습니다.

성능

이 구현은 각 add 연산이 O(log k) 시간 복잡도로 수행되므로, k개의 요소를 유지하면서 효율적으로 k번째로 큰 값을 찾을 수 있습니다.
초기 배열을 처리하는 경우 O(n log k) 시간이 소요됩니다.

결론

이 KthLargest 클래스는 우선순위 큐를 사용하여 k번째로 큰 값을 효율적으로 찾는 기능을 제공하며, 간단한 구조 덕분에 이해하기 쉽습니다. 이 방법은 특히 데이터의 양이 많거나, k의 값이 상대적으로 작을 때 성능상의 장점이 두드러집니다.

➕Priority Queue이란?

우선순위 큐(Priority Queue)는 각 요소가 우선순위를 가지며, 그 우선순위에 따라 요소를 처리하는 데이터 구조입니다. 일반적인 큐는 FIFO(First In, First Out) 방식으로 작동하지만, 우선순위 큐는 우선순위가 높은 요소가 먼저 처리됩니다. 따라서, 우선순위 큐는 우선순위에 따라 요소를 삽입하고 삭제하는 방식으로 작동합니다.

우선순위 큐의 주요 특징

우선순위:
- 각 요소는 우선순위를 가지며, 우선순위가 높은 요소가 먼저 큐에서 제거됩니다. 예를 들어, 높은 숫자는 낮은 숫자보다 낮은 우선순위를 가질 수 있습니다.
구현 방식:
- 우선순위 큐는 일반적으로 힙(Heap) 자료구조를 사용하여 구현됩니다. 최소 힙(min heap)을 사용하면 가장 작은 우선순위를 가진 요소가 루트에 위치하게 되고, 최대 힙(max heap)을 사용하면 가장 큰 우선순위를 가진 요소가 루트에 위치합니다.
연산:
- 삽입 (Enqueue): 새로운 요소를 우선순위에 따라 큐에 추가합니다. 시간 복잡도는 O(log n)입니다.
- 삭제 (Dequeue): 가장 높은 우선순위를 가진 요소를 제거하고 반환합니다. 시간 복잡도는 O(log n)입니다.
- Peek: 가장 높은 우선순위를 가진 요소를 제거하지 않고 반환합니다. 시간 복잡도는 O(1)입니다.

사용 예시

스케줄링: 작업의 우선순위에 따라 시스템 자원을 할당하는 데 사용됩니다. 예를 들어, 운영체제의 프로세스 스케줄링에서 우선순위가 높은 프로세스가 먼저 실행됩니다.
다익스트라 알고리즘: 최단 경로 알고리즘에서 현재 위치에서 가장 가까운 노드를 선택하기 위해 우선순위 큐를 사용합니다.
Huffman 코딩: 데이터 압축 알고리즘에서 각 문자의 빈도에 따라 우선순위를 정하고, 이를 기반으로 트리를 생성합니다.

➕Heap이란?

힙(Heap)은 완전 이진 트리의 일종으로, 특정한 성질을 가진 자료구조입니다. 주로 우선순위 큐를 구현하기 위해 사용되며, 두 가지 주요 유형인 최소 힙(min heap)과 최대 힙(max heap)이 있습니다.

힙의 기본 개념

완전 이진 트리: 힙은 완전 이진 트리 형태를 가지며, 모든 레벨이 완전히 채워져 있어야 합니다. 마지막 레벨은 왼쪽부터 채워질 수 있습니다.
힙의 성질
- 최소 힙(min heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 성질을 가집니다. 따라서 루트 노드는 항상 가장 작은 값입니다.
- 최대 힙(max heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은 성질을 가집니다. 따라서 루트 노드는 항상 가장 큰 값입니다.

힙의 주요 연산

삽입 (Insert)
- 새로운 요소를 힙에 추가할 때는 트리의 마지막 위치에 삽입하고, 부모와 비교하여 필요한 경우 위치를 조정합니다. 이 과정을 "상향 조정" 또는 "퍼콜레이션 업(percolate up)"이라고 합니다.
- 시간 복잡도: O(log n)
삭제 (Delete)
- 힙의 루트 요소(최소 힙의 경우 가장 작은 요소, 최대 힙의 경우 가장 큰 요소)를 삭제할 때는 루트 요소를 제거하고, 마지막 요소를 루트로 이동시킵니다. 그 후, 자식과 비교하여 필요한 경우 위치를 조정합니다. 이 과정을 "하향 조정" 또는 "퍼콜레이션 다운(percolate down)"이라고 합니다.
- 시간 복잡도: O(log n)
힙 생성 (Heapify)
- 배열에서 힙 구조를 생성하는 과정입니다. 배열의 중간부터 시작하여 하향 조정을 통해 힙을 만듭니다.
- 시간 복잡도: O(n)

힙의 활용

우선순위 큐: 힙은 우선순위 큐를 구현하는 데 사용됩니다. 최소 힙을 사용하면 가장 작은 요소를 빠르게 추출할 수 있습니다.
정렬 알고리즘: 힙 정렬(Heap Sort)은 힙을 이용한 정렬 알고리즘으로, O(n log n)의 시간 복잡도로 정렬할 수 있습니다.
그래프 알고리즘: 다익스트라 알고리즘(Dijkstra's Algorithm)과 같은 최단 경로 알고리즘에서도 힙이 사용됩니다.

예시

이 경우, 루트 노드 1은 가장 작은 값이며, 모든 부모 노드는 자식 노드보다 작거나 같습니다.

힙은 다양한 상황에서 효율적으로 데이터를 관리하고 처리하는 데 유용한 자료구조입니다.

yewon

이전 포스트

[99클럽 코테 스터디_ DAY 9] 상대적 순위

다음 포스트

[99클럽 코테 스터디_ DAY 10] K번째로 큰 요소

스터디

K번째로 큰 요소

💡나의 풀이

클래스 구조

작동 원리

결론

💡다른 사람의 풀이

클래스 구조

작동 원리

성능

결론

➕Priority Queue이란?

우선순위 큐의 주요 특징

사용 예시

➕Heap이란?

힙의 기본 개념

힙의 주요 연산

힙의 활용

예시

[99클럽 코테 스터디_ DAY 9] 상대적 순위

[99클럽 코테 스터디_ DAY 11] 정수 내림차순으로 배치

0개의 댓글