꿀잠

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/k-closest-points-to-origin/description/

원점에서 가까운 순서대로 좌표 k 개를 찾는 문제이다. 가까운 순서대로 정렬해야 하므로 PriorityQueue를 이용하여 해결하였다.

PriorityQueue를 이용할 때 원하는 방식으로 정렬하기 위해선 Comparator를 지정해주거나 class가 Comparable 인터페이스를 구현하면 된다. Point에 대하여 별도의 클래스를 생성했으므로 Comparable 인터페이스를 구현해주었다.

원점까지의 거리는 두 점의 차이점에 제곱을 각각 한 이후 루트를 해주어야 하지만, 원점의 좌표가 0인점, 그리고 루트 계산을 해주지 않아도 크기 비교는 할 수 있다는 점에서 루트 계산은 제거하였다.

import java.util.*;  
  
public class Solution {  
    public int[][] kClosest(int[][] points, int k) {  
  
        PriorityQueue<Point> pq = new PriorityQueue<>();  
  
        for(int i = 0; i < points.length; i++){  
            int x = points[i][0];  
            int y = points[i][1];  
            pq.add(new Point(x, y));  
        }  
  
        int[][] answer = new int[k][2];  
        while(k-- > 0){  
            Point point = pq.poll();  
            answer[k][0] = point.x;  
            answer[k][1] = point.y;  
        }  
  
        return answer;  
    }  
  
    private class Point implements Comparable<Point>{  
        int x;  
        int y;  
        int distFromOrigin;  
  
        Point(int x, int y){  
            this.x = x;  
            this.y = y;  
            this.distFromOrigin = x*x + y*y;  
        }  
  
        @Override  
        public int compareTo(Point o){  
            return this.distFromOrigin - o.distFromOrigin;  
        }  
    }  
}