꿀잠

https://leetcode.com/problems/median-of-two-sorted-arrays/description/

두 개의 숫자 배열이 주어질 때 전체 숫자의 중간 값을 찾는 문제이다. 이전에 풀었던 문제와 같은 형식의 문제였다. 당시에 풀었던 문제는 클래스를 만드는 문제였고, 이 문제는 중앙 값을 실제로 얻어내는 문제이다. 최종적으로 이번에 통과한 코드이다.

import java.util.*;  
  
public class Solution {  
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {  
  
        Median med = new Median();  
  
        for(int num: nums1){  
            med.addNum(num);  
        }  
  
        for(int num: nums2){  
            med.addNum(num);  
        }  
  
        return med.calcMedian();  
    }  
  
    private static class Median{  
  
        PriorityQueue<Integer> left = new PriorityQueue<>((a,b) -> Integer.compare(b,a));  
        PriorityQueue<Integer> right = new PriorityQueue<>();  
  
        private void addNum(int n){  
            if(left.isEmpty()){  
                left.add(n);  
            }else if(left.peek() > n){  
                left.add(n);  
            }else{  
                right.add(n);  
            }  
  
            while(right.size() > left.size()){  
                left.add(right.poll());  
            }  
  
            while(left.size() > right.size() + 1 ){  
                right.add(left.poll());  
            }  
        }  
  
        private double calcMedian(){  
            if((left.size() + right.size()) % 2 == 1){  
                return left.peek();  
            }else{  
                return (double)(left.peek() + right.peek()) / 2;  
            }  
        }  
    }  
}

아래 링크는 예전에 풀어봤던 이와 비슷한 문제와 풀이 내용이다.
https://leetcode.com/problems/find-median-from-data-stream/description/

당시에 풀었던 내용은 아래와 같다.
https://ygs3004.tistory.com/109

https://leetcode.com/problems/find-median-from-data-stream/description/

주어진 클래스의 메서드를 완성시키는 문제이다. 이 때 입력된 숫자 값들의 중간 값, 짝수개 일 경우 중간 값 두 가지를 더한 후 나눈 값을 리턴시켜야 하는 메서드가 존재한다. 일반적인 List, LinkedList를 이용한 후 size 값으로 인덱스를 찾을 경우 시간 초과에 걸리게 된다.

문제를 해결하기 위해서 정렬에 효율적인 PriorityQueue를 이용하고, 중간 값을 찾기 편하게 하기 위하여 두 구간으로 나누었다. left 구간은 right 값보다 작은 값들로 peek 할 경우 중간 값, 짝수 사이즈일 때는 작은 중간 값을 확인할 수 있다. right 구간은 peek 할 경우 짝수 사이즈일 때 큰 중간 값을 확인할 수 있다. 이를 위해서 left PriorityQueue는 내림차순으로 Comperator를 설정해주어야 한다.

addNum 함수는 값이 들어오는 함수이다. 기본적으로 left의 조건을 확인하고 추가하고, 아닐 경우 right에 추가한다. 하지만 left에만 값이 쌓일 수 있는 경우의 수가 있으므로 사이즈를 비교해서 바로 left,right 균형을 맞춰 주었다.

addNum 함수와 PriorityQueue 두 구간으로 나누기를 완성했으면 중간 값을 구하는 메서드는 간단해진다. 홀 수 사이즈는 left에서 확인 가능하고 짝 수 사이즈는 left와 right에서 확인 가능하다. 단 값이 비어있는 경우 peek() 메서드에서 NullPointerException 이 발생할 수 있으므로 예외 값을 별도로 분기처리해주었다.

import java.util.*;  
  
class MedianFinder {  
  
    PriorityQueue<Integer> left;  
    PriorityQueue<Integer> right;  
  
    public MedianFinder() {  
        left = new PriorityQueue<>((a,b) -> Integer.compare(b, a));  
        right = new PriorityQueue<>();  
    }  
  
    public void addNum(int num) {  
        if(left.isEmpty()){  
            left.add(num);  
        }else if(left.peek() > num){  
            left.add(num);  
        }else{  
            right.add(num);  
        }  
  
        while(right.size() > left.size()){  
            left.add(right.poll());  
        }  
  
        while(left.size() > right.size() + 1){  
            right.add(left.poll());  
        }  
    }  
  
    public double findMedian() {  
  
        double median = 0;  
        int size = left.size() + right.size();  
          
        if(size == 0){  
            return median;  
        }else if(size % 2 == 0){  
            median = (double)(left.peek() + right.peek())/2;  
        }else{  
            median = left.peek();  
        }  
  
        return median;  
    }  
}  
  
/**  
 * Your MedianFinder object will be instantiated and called as such: 
 * MedianFinder obj = new MedianFinder(); 
 * obj.addNum(num); 
 * double param_2 = obj.findMedian(); 
 */

https://ygs3004.tistory.com/manage/newpost/?type=post&returnURL=%2Fmanage%2Fposts%2F

주어지는 Task를 실행하기 위한 시간을 구하는 문제이다. 같은 Task를 실행하기 위해선 n 만큼의 시간이 지나야 한다는 제한 조건이 있다.

Task를 실행하기 위하여 반복되는 Task를 우선 실행하게 하기로 했다. PriorityQueue를 이용하여 Task의 repeat을 기준으로 정렬 되도록 하였다. 단 이때 n 만큼의 시간이 더 필요한 경우를 체크해야 했기 때문에 현재 실행이 불가능한 경우는 next로 이동시켜 주었다. 모든 Task가 실행이 불가능한 경우 next로 전부 이동이 되며 while 문이 종료된다. 이 때는 다음 루프로 cnt가 증가하며 idle이 실행된 것으로 간주할 수 있다. 실행 가능한 Task가 있을 경우 해당 task를 poll한 상태로 나머지를 next로 이동시켜 주어서 문제를 해결했다.

import java.util.*;  
  
public class Solution {  
    public int leastInterval(char[] tasks, int n) {  
        PriorityQueue<Task> pq = new PriorityQueue<>();  
        int[] repeats = new int[26];  
  
        // 문자별 반복 횟수 체크  
        for(int i = 0; i < tasks.length; i++){  
            char c = tasks[i];  
            repeats[c - 'A']++;  
        }  
  
        // 문자 반복 및 값 정보 pq 에 삽입,  
        // n의 최대값이 100이므로 초기 lastIdx를 충분히 낮은 값인 -101로 주었다.  
        // Integer.MIN_VALUE 처럼 극한 값을 주면 오버플로우 발생 가능  
        for(int i = 0; i < repeats.length; i++){  
            if(repeats[i] > 0){  
                char c = (char)(i + 'A');  
                pq.add(new Task(repeats[i], c, -101));  
            }  
        }  
  
        int cnt = 0;  
        while(!pq.isEmpty()){  
            PriorityQueue<Task> next = new PriorityQueue<>();  
            cnt++;  
  
            // 실행 할수 있는 Task 가 있는지 확인  
            while(!pq.isEmpty()){  
                Task task = pq.poll();  
                int lastIdx = task.lastIdx;  
                if(cnt - lastIdx > n){  
                    task.lastIdx = cnt;  
                    task.repeat--;  
  
                    if(task.repeat > 0){  
                        next.add(task);  
                    }  
                    break;  
  
                }  
                // Task 가 next로 전부 이동될 동안 실행 불가능할 경우 idle                
                next.add(task);  
            }  
  
            // 나머지 Task next 로 이동  
            while(!pq.isEmpty()){  
                next.add(pq.poll());  
            }  
  
            // next pq를 이용하여 다음 체크  
            pq = next;  
        }  
  
        return cnt;  
    }  
  
    private static class Task implements Comparable<Task>{  
        int repeat;  
        char value;  
        int lastIdx;  
  
        Task(int repeat, char value, int lastIdx){  
            this.repeat = repeat;  
            this.value = value;  
            this.lastIdx = lastIdx;  
        }  
  
        @Override  
        public int compareTo(Task o){  
            return Integer.compare(o.repeat, this.repeat);  
        }  
    }  
}

코드를 완성하고 나서 결과가 다른 정답 코드에 비해 느린 편으로 나왔다. 다른 코드의 방식은 규칙성을 이용해 일종의 수학적 공식을 만드는 방식이었다. 하지만 실제 해당 코드에서 task가 진행되는 동안에 추가적인 동작이 필요하다면 이용할 수 없기에 좋은 방법은 아닌듯하다. 수학적인 방식이 아니라 프로그래밍 방식의 해결 방법을 위해서는 PriorityQueue를 쓰는게 좋은 풀이라고 생각한다.

https://leetcode.com/problems/kth-largest-element-in-an-array/description/

sort를 쓰지 않고 배열의 K번째로 큰 요소를 찾는 문제이다.
알고리즘을 복습하려고 따라가고 있는 리트코드 로드맵상에선 Heap & Priority Queue로 지정되어있어 Priority Queue를 이용해서 풀었다.

사실 PriorityQueue도 sort를 이용하는게 아닌가 하는 의구심이 들기는 한다.
하지만 Arrays.sort()를 이용하여 문제를 풀 경우 오류를 내뱉었다.

문제에서 PriorityQueue를 사용시 오류가 발생하지 않으며 이는 PriorityQueue를 허용한다는 의미이며

그것이 문제의 의도라고 확인하였다.
문제 풀이에 성공한 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public int findKthLargest(int[] nums, int k) {  
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);  
        // PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());  
        for (int num : nums) {  
            pq.add(num);  
        }  
  
        while (k-- > 1) {  
            pq.poll();  
        }  
  
        return pq.poll();  
    }  
}

PriorityQueue 는 기본적으로 Integer 의 compareTo 메서드에 따라 오름차순으로 정렬하기 때문에 생성시 새로운 compareTo 메서드를 오버라이드 해야한다. Collections.reverseOrder()를 이용해 간단히 역순 정렬을 할 수도 있으며, 직접 수식을 compareTo 메서드에 오버라이드 해주는 것도 방법이다. 이 때 화살표 함수로 손쉽게 메서드를 표기할 수 있다.

PriorityQueue에 nums 배열을 넣은 후에는 간단하다. k번째로 큰수이기 때문에 k번째의 수를 뽑아내주면 된다. k-1 번째까지 뽑은 후 리턴시 k번째 수를 poll하여 반환하였다.