프로그래머스 Lv2 요격 시스템 문제

• 프로래머스 Lv2 요격 시스템 문제
  • 문제를 읽고 난 후의 분석
    1. 자원을 최소로 사용하여 요격하기
    2. 맵은 2차원 배열이며 a나라의 미사일은 x축과 평행하게 날아오고, b나라의 방어미사일은 y축에 평행하게 발사
    3. 방어미사일은 해당 발사지점의 y축에 속한 x축의 모든 미사일을 관통할 수 있으며 한발로 여러 발 제거 가능
    4. 개구간(s, e)으로 표현되는 미사일은 s,e 좌표에선 미사일을 발사하지 못하므로 방어 불가
    5. 요격 미사일은 실수 x 축에서도 발사가 가능
    6. 배열 내 요소의 최대값은 1억이 최대이므로 int는 사용가능
    7. 길이 또한 5만이 최대이므로 int사용 가능
    8. 예시 그림을 보니 이미 관통한 미사일 경로는 다른 미사일 경로 관통 시, 같이 관통되는 일이 있으면 안됨
  • 해당 문제의 난이도 상승 원인
  • 해당 문제를 해결한 방법
  • 해당 문제를 해결였던 과정
    1. 이전에 해결하였던 겹칩에 관한 문제가 떠올라 해당 문제에 접목해보니 '겹칩구간 발생' 에 대한 것이라는 생각이 듦
    2. 또한 경우의 수 + 최소값 구하기 문제류 이므로 DFS와 BFS가 생각났으나 BFS는 최단 거리에서 적용이 가능하기 때문에 DFS를 사용하기로 결정
    3. 처음 계획은 먼저 타겟배열을 받고 이 배열을 [0]를 기준으로 오름차순 배열 후 DFS를 돌리는 것으로 잡음
    4. dfs 식으로 작성 후 테스트케이스 완료까지 되는 것을 확인한 후에 코드 테스트를 실행하니 전체 경우중 2가지를 제외하고 전부 시간초과가 발생하여 문제점 분석을 시작
    5. 분석 후 문제점을 확인하니 DFS 쪽에 있었고 DFS가 아닌 Greedy 방식을 사용해야했음을 알게 되었다.원래 DFS를 사용하려한 이유는 이 문제가 완전 탐색문제라고 판단하여 시간을 기준으로 정렬 후 처리하려고 했는데 오히려 이 문제는 시간을 기준으로 정렬하고 해당 시간 내에서 최적의 선택을 해야하기 때문에 Greedy방식이었던 것이다
    6. DFS를 사용하지 않은 1번 전체순환을 이용한 Greedy 방식으로 변경 후 코드 테스트를 해보았고 아까보단 2개 더 많은 항목을 정답으로 하였으나 그럼에도 오류가 발생하여 다시 분석
    7. 디버그 모드 실시간 분석하면서 확인해보니 순환문 내에서 내가 의도한 내용인 시작범위는 큰 값으로, 종료범위 적운 겂으로 설정하는 것과는 다르게 코드가 작동하는 부분이 있어 해당 부분 수정후 다시 코드 제출ㅇ하니 정답처리 됨
  • 문제의 핵심
    • DFS를 쓸 상황과 Greedy를 쓸 상황을 판단하는 것
    • 들어온 데이터를 전처리해야하는 지 말아야하는 지

import java.util.Arrays;

public class Lv2InterceptSystem {
    public static void main(String[] args){
        int[][] targets = {
                {4, 5}, {4, 8}, {10, 14}, {11, 13}, {5, 12}, {3, 7}, {1, 4}
        };
        solution(targets);
    }

    public static boolean isOverLapCheck(int[] a, int[] b){
        //a1<=b2 && b1 <= a2
        return a[0] < b[1] && b[0] < a[1];
    }

    public static int solution(int[][] targets){
        Arrays.sort(targets, (a, b) -> Integer.compare(a[1], b[1]));

        for(int[] t: targets) System.out.println(t[0] + ", " + t[1]);
        System.out.println("-------------------------");

        int answer = 0;
        int[] compareBase = null;

        for(int i = 0; i < targets.length; i++){
            if(compareBase == null){
                compareBase = new int[]{targets[i][0], targets[i][1]};
                answer++;
                continue;
            }

            if(isOverLapCheck(compareBase, targets[i])){
                compareBase[0] = Math.max(compareBase[0], targets[i][0]);
                compareBase[1] = Math.min(compareBase[1], targets[i][1]);
            }
            else{
                compareBase = new int[]{targets[i][0], targets[i][1]};
                answer++;
            }
        }

        return answer;
    }
}