[PS] 프로그래머스-요격시스템 (Greedy) with JAVA

 

https://school.programmers.co.kr/learn/courses/30/lessons/181188

프로그래머스

 

 

◎ 문제풀이

 

폭격미사일은 X 좌표 범위(start,end)를 가지고 요격미사일은 특정 x좌표에서 발사될 때, 최소한의 요격미사일 발사로 폭격미사일을 요격해야하는 문제이다. 

 

주어진 폭격미사일 범위를 end좌표로 오름차순 정렬하는 것이 중요하다. 

 

요격미사일은 폭격미사일이 끝(end)나는 지점에서 최소한 한 개가 발사되어야 하기 때문이다. 그러므로 폭격미사일 배열을 end를 기준으로 오름차순 정렬해야 한다. 

 

0) 정렬된 폭격미사일 배열을 처음부터 하나씩 접근한다.

1) 현재 end를 기준으로 요격미사일 1개가 발사한다.

2) 다음 폭격미사일의 start가 현재 end보다 작으면 발사된 요격미사일에 요격된다. 

3) 다음 폭격미사일의 start가 현재 end보다 크면 요격되지 않으므로 새로운 요격미사일을 발사한다. 

4) 요격미사일이 발사 될 때마다 카운트 한다. 

 

 

◎ 코드 

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        // end를 기준으로 오름차순 정렬
        Arrays.sort(targets,(o1,o2)-> o1[1]-o2[1]);
        
        int currEnd = -1;
        int ans = 0;
        
        // 정렬된 폭격 미사일 하나씩 접근하기
        for(int[] target : targets){
            
            // 첫 폭격미사일인 경우
            if(currEnd == -1){
                ans++; // 요격미사일 카운트
                currEnd = target[1];
                continue;
            } 
            
            // start가 현재 end보다 작으면 이미 발사된 요격미사일에 요격됨
            if(target[0] < currEnd) continue;
            
            ans++; // 요격미사일 카운트
            currEnd = target[1]; // 현재 end update하기

        }
        
        return ans;
 
    }
}