[프로그래머스] 요격 시스템(정렬, 그리드 / 자바)

문제 링크

프로그래머스

 

문제

주황색은 폭탄이 날라가는 구간이다. 우린 이 폭탄을 미사일로 요격해야 한다. 이때 최소로 필요하는 요격 미사일 개수를 구하면 되는 문제다.

입출력 예 설명 사진 - 프로그래머스 출처

 

풀이

어떤 유형의 문제인지 파악하는 것이 첫 번째이다.

정렬, 그리드 문제이다.

그리드 알고리즘 : 매 순간 최적이라고 생각되는 선택을 해나가면서 최종적인 해답에 도달하는 방식

 

1. 이차원 배열을 첫번째 원소 기준으로 오름차순으로 정렬한다.
2. 카운트를 해주며 요격 구간을 변경한다.
3. 이전 폭탄구간에  현재 폭탄 시작점이 들지 않으면 카운트를 한다. 폭탄 구간을 현재 폭타구간으로 바꾼다.
4. 만약, 이전 폭탄구간에  현재 폭탄 시작점이 든다면 카운트를 하지 않는다.
5. 요격 구간을 변경하는 기준은 이전 시작점과 현재 시작점을 비교한다. 더 큰 것이 시작점이다. 이전 끝나는 점과 현재 끝나는 점을 비교한다. 더 작은 것이 끝나는 점이다. 

 

import java.util.*;

class Solution {
    public int solution(int[][] targets) {
        // 첫 번째 구간을 이미 포함하므로 answer를 1로 초기화
        int answer = 1;

        // targets 배열을 첫 번째 요소를 기준으로 오름차순 정렬
        Arrays.sort(targets, (x, y) -> x[0] - y[0]);

        // 첫 번째 구간을 초기값으로 설정
        int currentStart = targets[0][0];
        int currentEnd = targets[0][1];

        for (int i = 1; i < targets.length; i++) {
            int nextStart = targets[i][0];
            int nextEnd = targets[i][1];

            // 현재 구간의 끝점과 다음 구간의 시작점이 겹치는 경우
            if (currentEnd > nextStart) {
                // 겹치는 구간의 끝점을 업데이트
                currentEnd = Math.min(currentEnd, nextEnd);
            } else {
                // 겹치지 않는 경우, 새로운 구간으로 간주하고 카운트 증가
                currentStart = nextStart;
                currentEnd = nextEnd;
                answer++;
            }
        }

        return answer;
    }
}