LeetCode Daily 문제풀기

452. Minimum Number of Arrows to Burst Balloons

풍선은 Y 축에 관계없이 주어진 배열에 따라 x 축으로 길게 형성되어있다. 최소한의 화살을 쏴서 풍선을 터트려야 하는데.. 음 어떻게 풀지 감이 잘 안 온다. 뭔가 그리디 문제 같은데..

첫 번째 접근방법

좌우 차이를 이용해 가장 큰 것부터 제거하면서 그 범위를 기록해 놓는 것이다.  (x)

-> 1-5  1-2, 4-5 이렇게 주어진다면 가장 큰 1-5 가 범위가 기록되고 1-2, 4-5 모두 한 번에 1-5 라인에 소거되기에 탈락

두 번째 접근방법

좌우 차이를 이용해 가장 작은 것부터 제거하면서 그 범위를 기록해 놓는 것

-> 1-5, 1-2, 4-5 음? 뭔가 될 거 같다. 바로 PriorityQueue를 이용해 정렬 후 뽑아가면서 계산을 해보자.

class Solution {
    public int findMinArrowShots(int[][] points) {
        PriorityQueue<int[]> q
                    = new PriorityQueue<>((a,b) ->(a[1]-a[0])-(b[1]-b[0]));

        for(int[] arr : points){
            q.offer(arr);
        }

        List<int[]> list = new ArrayList<>();
        while(!q.isEmpty()){
            int[] poll = q.poll();
            boolean range = false;
            for(int[] arr : list){
                boolean a = poll[0] <= arr[0] && arr[0] <= poll[1];
                boolean b = poll[0] <= arr[1] && arr[1] <= poll[1];
                if(a || b){
                    range = true;
                    break;
                }
            }
            if(!range) list.add(poll);
        }
        return list.size();
    }
}

36 번째 테스트 케이스에서 깨진다. 왜? 3-5, 5- 7,1-4 이런 경우 3-5가 범위가 찍히고 5-7 이 찍힌다. 이러면 화살은 5번을 쏴야 하지만 1-4 또한 소거된다. 3을 기준으로 분류되기 때문에 이렇게 범위를 이용하는 것이 아닌 하나의 점을 찍어서 구현을 해야 할 것 같은데...

사실 위 방법 말고도 다양한 방법으로 구현해봤으나 다 실패했다.

하.. 멘털 갈린다. 설루션 가서 접근법을 먼저 살펴보고 오자. 

한 번에 많은 화살로 최대한 많은 풍선을 터트려야 한다. 그렇다면 가장 많은 풍선을 터트릴 방법 중 하나는 주어진 범위 최소 혹은 최대 값을 이용하면 판별하기 쉽다. 그러나 모든 가지의 경우의 수를 계산할 필요는 없다 왜? 

정렬을 이용해 오른쪽 숫자별로 기준으로 정해서 그 포인트 별로 화살을 날려주면 되기 때문이다.

balloons = [[7,10], [1,5], [3,6], [2,4], [1,4]]
정렬 이후 
balloons = [[2,4], [1,4], [1,5], [3,6], [7,10]]

하... 이 쉬운 걸 파악 못해서 1시간을 저러고 있으니 참 그렇다.

class Solution {
    public int findMinArrowShots(int[][] points) {
        PriorityQueue<int[]> q = new PriorityQueue<>(
                    (a,b) -> a[1]-b[1]
            );
            Arrays.stream(points).forEach(q::offer);

            int cnt = 0;

            while(!q.isEmpty()){
                int[] cur = q.poll();
                while(!q.isEmpty() && q.peek()[0] <= cur[1] &&  cur[1] <= q.peek()[1]){
                    q.poll();
                }
                cnt++;
            }
            return cnt;
    }
}

항상 화살은 endPoint 기준으로 날려준다는 로직을 세우고 

우선순위 큐를 활용해 정렬을 했고, 큐를 돌면서 다음 범위를 확인한 후 지워줄지 말지를 정하고 날려준다.

 

이것 외에 배열 정렬을 통해 해결하는 방법도 있다.

 

class Solution {
    public int findMinArrowShots(int[][] points) {
        Arrays.sort(points, (a,b) -> Integer.compare(a[1], b[1]));
        int cnt = 1;
        int current = points[0][1];
        for(int i=1;i<points.length;i++){
            if(current < points[i][0]){
                cnt++;
                current = points[i][1];
            }
        }
        return cnt;
    }
}

current 가 현재 화살을 소는 타깃 즉 endPoint 가 된다. 

 

Simillar Question 찍어서 비슷한 문제 더 풀어야겠다 화나서 안 되겠다.

 

56. Merge Intervals

이번에는 합쳐주는 방식이다. 양 좌우측 사이에 겹치는 오버래핑되는 수가 있다면 합쳐서 늘려주면 된다.

위에서는 pq를 이용했으니 이번에는 배열방식으로 풀어보자.

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->a[0]-b[0]);
            
        List<int[]> answer = new ArrayList<>();

        int min = intervals[0][0];
        int max = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {
            if(min <= intervals[i][0] && intervals[i][0] <= max){
                max = Math.max(intervals[i][1],max);
            }else{
                answer.add(new int[]{min,max});
                min = intervals[i][0];
                max = intervals[i][1];
            }
        }
        answer.add(new int[]{min,max});
        return answer.toArray(new int[answer.size()][]);
    }
}

 

 

이번에는 합치는 로직이다 보니 위에 와는 달리 작은 값이 중요하다 현재 값 사이에  정렬된 배열의 다음 왼쪽값이  포함되느냐 가 주된 로직이다.

forLoop 가 끝나고 한 번 더 추가하는데 이는 마지막까지 모든 수를 업데이트하고 나서 추가가 안 되는 경우를 위해 이렇게 따로 추가한다.

사실 틀리기 전까지 몰랐다. 그래서 추가적으로 위와 같이 작성했다.

 

435. Non-overlapping Intervals

이번에는 겹치는 부분을 제거해주는 로직을 구현하면 된다.

위와 동일하게 좌측 기준으로 정렬 을 하고 오른쪽 값을 업데이트해나가면서 오른쪽 값과 새로 들어온 왼쪽 값을 비교하면 된다.

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));

        int cur = intervals[0][1];
        int cnt = 0;

        for(int i=1;i<intervals.length;i++){
            if(cur > intervals[i][0]){
                cnt++;
                cur = Math.min(intervals[i][1],cur);
            }else{
                cur = intervals[i][1];
            }
        }
        return cnt;
    }
}

어으 사실 이 문제도 여러 번 틀렸다. 접근방법은 비슷했으나. 어떻게 다음으로 걸러 주는지 분기를 나누는 부분에서 버벅 거렸다..

 

결론 그리디 문제 너무 싫다.