프로그래머스

문제

풀이

public class Pro_요격시스템 {
    public int solution(int[][] targets) {
        Arrays.sort(targets, (a,b) ->{
            return a[1] - b[1];
        });
        int point = -1;
        int cnt = 0;
        for(int i = 0; i < targets.length; i++){
            int left = targets[i][0];
            int right = targets[i][1];
            if(left >= point){
                cnt++;
                point = right;
            }
        }
        return cnt;
    }
}

리뷰

풀이 자체는 어렵지 않은 문제였으나, 실수인 x 좌표에서도 미사일을 발사할 수 있다는 문장 때문에 헷갈렸던 문제다.

1. 먼저 미사일의 왼쪽 위치를 기준으로 오름차순 정렬을 한다.
   • 어차피 왼쪽 위치의 기준으로 오름차순 정렬 되어 있고, 문제에서 하나의 미사일은 해당 x좌표에 걸쳐있는 모든 미사일을 요격할 수 있다고 했으므로 굳이 미사일의 오른쪽 위치를 기준으로 정렬해줄 필요는 없다.
2. 요격 위치(point)를 -1로 초기화하고, 만약 target의 왼쪽 위치(left)가 요격위치보다 크거나 같다면 미사일 수(cnt)에 1을 더하고 point를 target의 오른쪽 위치(right)로 변경한다.
   • 실수 x좌표에서도 미사일을 발사할 수 있다고 하였으므로 요격 미사일을 오른쪽 위치에서 -0.1만 이동하고 발사한다고 생각하고, 요격 위치(point)를 target의 right로 잡으면 target의 범위 안에 포함되어 있는 모든 미사일을 한꺼번에 요격이 가능하다.

알고리즘은 알고리즘 자체를 아는 것도 중요하지만, 해결 방법을 알아내는 훈련도 정말 중요한 것 같다.