[Leetcode] sliding window median java

문제 설명 

k개의 정수가 주어질 때에, 그 중 중앙 값을 찾는 문제이다.

만약 1, 3, -1이 있다면 1이 중앙 값이다. 

Input으로 nums 배열이 주어지고, Output으로 중앙 값을 출력해준다. 

문제 접근

우선 순위 Queue를 2개 운영한다.

- PriorityQueue<Integer> lowerQueue = new PriorityQueue<>(Comparator.reverseOrder());

- PriorityQueue<Integer> upperQueue = new PriorityQueue<>();

단, 계속해서 중앙 값을 갱신해주기 위해서는 lowerQueue는 높은 숫자들을 빼주어야 하기 때문에 Comparator.reverseOrder()로 설정해준다. 

 

그리고 나서 제거, 추가, 정렬 3단계로 진행되게 된다.

먼저 for문을 통해서 0부터 arr.length-k까지 탐색하면서 탐색이 끝난 arr[i] 을 제거해준다. 

제거해주고 나서 arr[i+k]를 통해서 다음 인덱스 값을 추가해준다. 

 

그리고 나서 크기 조정을 해주는데, 가운데 값을 upperQueue의 첫번째에 넣어주기 위해서 정렬을 해준다.

- upperQueue의 크기가 k/2 +1보다 작은 경우, lowerQueue에서 큰 숫자 1개를 빼서 upperQueue에 넣어준다.

- upperQueue의 크기가 k/2 +1보다 큰 경우, upperQueue에서 작은 숫자 1개를 빼서 lowerQueue에 넣어준다.

 

소스 코드

import java.util.*;

public class slidingWindowMedian {
    // 슬라이딩 윈도우 중앙값
    public static void main(String[] args) {
        int[] arr = {4, 2, 6, 4, 2, 3};
//        int[] arr = {4, 2, 6, 4, 2, 3,1,7};
        System.out.println(solution(arr, 3));
    }
    public static int[] solution(int[] arr, int k){
        int[] window = new int[k];
        PriorityQueue<Integer> lowerQueue = new PriorityQueue<>(Comparator.reverseOrder());
        PriorityQueue<Integer> upperQueue = new PriorityQueue<>();
        System.arraycopy(arr, 0, window, 0, k);
        Arrays.sort(window);

        for(int i=0; i<k/2; i++){
            lowerQueue.offer(window[i]);
        }
        for(int i=k/2; i<k; i++){
            upperQueue.offer(window[i]);
        }

        ArrayList<Integer> result = new ArrayList<>();
        result.add(upperQueue.peek());

        for(int i=0; i<arr.length-k; i++){
            // 제거
            if(arr[i] == upperQueue.peek()){
                upperQueue.poll();
            }else if(arr[i] < upperQueue.peek()){
                lowerQueue.remove(arr[i]);
            }else{
                upperQueue.remove(arr[i]);
            }

            // 추가
            if(arr[i+k] < upperQueue.peek()){
                lowerQueue.offer(arr[i+k]);
            }else{
                upperQueue.offer(arr[i+k]);
            }

            // 정렬
            if(upperQueue.size() < k/2 +1){
                upperQueue.offer(lowerQueue.poll());
            }else if(upperQueue.size() > k/2 + 1){
                lowerQueue.offer(upperQueue.poll());
            }
            
            result.add(upperQueue.peek());
        }

        for (int i = 0; i < result.size(); i++) {
            System.out.println(result.get(i));
        }

        return result.stream()
                .mapToInt(i->i)
                .toArray();
    }
}

 

 

https://leetcode.com/problems/sliding-window-median/

Sliding Window Median - LeetCode