[Programmers] 요격시스템 (Lv.2) 2023/6/3

 

문제 제목	정답률	난이도
요격시스템	33%	Lv.2

프로그래머스

 

문제요약

B 나라가 A 나라의 모든 폭격 미사일을 요격시킬때의 최소 요격 미사일 개수를 구하여라

조건 1) A, B 나라의 미사일은 2차원 공간에 존재한다.

조건 2) A 나라의 폭격 미사일은 x축과 수평으로 발사되며 열린구간(a, b)로 표시된다.(경계 구간을 포함하지 않음)

조건 3) B 나라의 요격 미사일은 x축과 수직으로 발사되며 해당 구간에 있는 모든 A나라 미사일을 요격시킬 수 있다.

 

 

풀이

Step1. x축 기준으로 A나라의 폭격 미사일 정렬

 

Step2. 이전에서 필요한 최소 구간을 기준으로 미사일 추가 여부 판단

• 이전의  A나라의 폭격 미사일 구간이 이전에 필요한 최소구간에서 벗어나면 미사일 추가
• A나라의 폭격 미사일 구간이 이전에 필요한 최소 구간보다 작으면 최소 구간 업데이트
• A나라의 폭격 미사일 구간이 이전에 필요한 최소 구간보다 같거나 크면 PASS

 

코드

import java.util.*;
class Solution {
    public int solution(int[][] targets) {
        // 1. X축 기준으로 정렬
        Arrays.sort(targets, (o1, o2) -> {
            return o1[0]-o2[0]; 
        });
        
        int answer = 0;
        int end_x=0;
        
        // 2. 이전의 최소구간과 A국의 현재 폭격 미사일 구간을 비교
        for(int i = 0; i < targets.length; i++) {
            if (end_x<=targets[i][0]){ // (1)범위가 다르면
                answer+=1;
                end_x=targets[i][1];
            }else if(end_x>targets[i][1]){// (2)범위가 작으면->범위 수정
                end_x=targets[i][1];
            }
        }
        return answer;
    }
}