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

문제 - 요격 시스템

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

문제 접근 방식

타겟의 끝 지점을 기준으로 정렬하고, 뒤에 나오는 타겟이 범위 안에 들어가는 지 확인하며 카운트를 늘려가는 방식

대표적인 그리디 문제 중 하나이다.
풀이 코드 자체는 상당히 짧지만, 구현 방식을 생각해내는데 시간이 오래 걸렸다.

타겟의 끝나는 점을 기준으로 정렬을 하고, 그 다음 타겟의 시작점이 타겟의 end보다 큰지 작은지 확인해주면 쉽게 풀리는 문제이다.

정답코드

import java.util.*;


class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        Arrays.sort(targets, Comparator.comparingInt(a -> a[1]));
        
        int[] now = {0, 0};
        
        for (int[] target : targets) {
            if (now[1] > target[0]) {
                continue;
            }
            now = target;
            answer++;
        }
        
        return answer;
    }
}

이 문제를 풀고 배운 점은

그리디 문제라고 생각된다면, 정렬을 어떻게 할지를 먼저 생각해보자
: 정렬만 잘 된다면 그 이후로 비교하는 방법은 쉽게 생각해 낼 수 있을지도 모른다.