[프로그래머스] 요격 시스템

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/181188

이 문제는 문제의 조건을 구현하면 풀 수 있습니다. 문제의 조건이 바로 떠오르지 않아 어렵게 느껴질 수 있는데 미사일의 위치를 기준으로 요격 미사일 위치를 정할 수 있습니다.

미사일이 하나도 설치가 되어 있지 않을 경우 미사일을 요격하기 위해 미사일을 추가하고 가장 마지막 미사일의 정보를 기억합니다. 다음 미사일 정보를 가져올 때 이전 미사일의 구간 내에 존재한다면 요격 미사일을 하나 더 설치할 필요가 없기 때문에 continue로 넘어가고 다른 구간일 경우 요격 미사일을 추가합니다.

여기서 중요한 점은 크게 2가지입니다. 첫 번째로 미사일을 정렬하지 않으면 미사일을 탐색하는 과정에서 이전에 탐색한 미사일 정보를 기억하고 있지 않아 중복 체크될 우려가 있습니다. 두 번째는 개구산의 시작과 끝점에서는 요격이 불가능하다는 것입니다. 따라서 미사일 정보를 기억할 때 끝 값을 기준으로 기억하고 끝값만을 continue 문 내부에서 포함시켜야 시작과 끝에서 요격이 되지 않습니다.

다음은 코드입니다.

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        int turrets = 0;
        
        Arrays.sort(targets, (o1,o2) -> {return o1[1]-o2[1];});
        int missile = -1;
        for(int[] target : targets){
            if(missile == -1){
                turrets++;
                missile = target[1];
            }
            
            if(target[0] < missile && target[1] >= missile) continue;
            
            turrets++;
            missile = target[1];
        }
        
        return turrets;
    }
}