452. Minimum Number of Arrows to Burst Balloons (해석 + 풀이)

조건:

• 1 <= points.length <= 105
• points[i].length == 2
• -231 <= xstart < xend <= 231 - 1

 

의역: 풍선들의 x좌표 범위의 정보가 들어있는 2차원 배열이 주어질 때 ex [1,3] 이면 1~3 사이에 풍선이 존재

 해당 범위 안에 화살을 쏘면 풍선이 터진다고 할 때 ex [1,3] 이면 1, 2, 3 위치를 쏘면 풍선이 터짐

 모든 풍선을 터트리는데 필요한 최소한의 화살의 갯수는 몇 개 인가?

(요약) 벽에 풍선이 달려있는 상태에서 화살을 쏠때 모든 풍선을 터트리는데 최소한으로 필요한 화살의 갯수는 몇 개인가?

의역: 4개의 풍선의 좌표가 겹치는 부분은 [2, 8], [1, 6] -> [1,6] 즉 1~6 사이를 쏘면 해당 풍선 2개가 터짐

[7, 12], [10, 16] 7~12 사이를 쏘면 해당 풍선 2개가 터짐 즉 2발만 있다면 모든 풍선을 터트리는 것이 가능

의역: 4개의 풍선이 좌표가 겹치는 부분이 없기 때문에 각자 한 발씩 쏴서 일일이 터트려야 하기에 return 4

의역: 4개의 풍선이 겹치는 범위는 [1,2], [2,3] -> 2 [3,4], [4,5] -> 4 임으로 2와 4의 위치에 한 발씩 쏜다면 모든 풍선이 터지기 때문에 모든 풍선이 터지는데 필요한 화살의 수는 2개

 

풀이: 이차원 배열의 각 배열의 2번째 요소를 기준으로 정렬하여 공통 범위 안이면 pass 밖이면 ans++ 

참조한 사람의 풀이

 

class Solution {
    public int findMinArrowShots2(int[][] points) {
        if(points.length==0) return 0;
        // 예시: points = [[7,10], [1,5], [3,6], [2,4], [1,4]] 을
        Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
        // 예시: points = [[2,4], [1,4], [1,5], [3,6], [7,10]] 으로
        int ans = 1; // 첫 번째 풍선을 쏜다 가정
        int position = points[0][1]; // 첫 번째 풍선의 가장 오른쪽 x축 좌표 위치
        for(int i=1;i<points.length;i++){
        	// 앞에서 풍선을 쐇을때 같이 터진 경우
            if(position>=points[i][1]){
                continue;
            }
            // 그렇지 않은 경우  
            ans++;
            position = points[i][1];
        }
        return ans;
    }
}

+ Arrays.sort() 함수를 통해 2차원 배열을 정렬하는 방법이 익숙하지 않다면 좋은 글이 있어 같이 링크 올립니다.

https://ifuwanna.tistory.com/328

 

+ 번외로 sort() 함수 대신 TreeMap을 썼던 방법 

class Solution {
	public int findMinArrowShots(int[][] points) {
        if(points.length==1) return 1;
        int ans = points.length;
        TreeMap<Integer,Integer> tmap = new TreeMap<Integer, Integer>();
        for(int i=0;i<points.length;i++){
            if(tmap.containsKey(points[i][0])) {
                int c = tmap.get(points[i][0])<points[i][1]?tmap.get(points[i][0]):points[i][1];
                tmap.put(points[i][0], c);
                ans--;
            }
            else {
                tmap.put(points[i][0], points[i][1]);
            }
        }
        int pre = Integer.MIN_VALUE;

        Iterator<Integer> it = tmap.keySet().iterator();
        while(it.hasNext()){
            int tmp = it.next();
            int value = tmap.get(tmp);
            if(pre>=tmp){
                ans--;
                pre = pre<value?pre:value;
            }
            else{
                pre = value;
            }
        }
        return ans;
    }
}

 

링크: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/