JAVA 기초 알고리즘 - [프로그래머스] 요격 시스템 (정렬은 Arrays.sort()이고, overriding이 가능하다)

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

프로그래머스

버스타고 집에 돌아오는 길에 일단 알고리즘을 어떻게 짤지 고민을 좀 해보게 되는 문제였습니다.

그래서, 기초 알고리즘이라고 하기에는... 좀 그렇지 않나 싶긴 하지만 그래도 Arrays.sort를 구현해볼 수 있는 문제였기에 넣었습니다!

일단 간단하게 로직을 생각해 보았습니다.

시작 지점으로 정렬을 하면 가장 빠르게 시작하는 타겟은 무조건 총을 쏴야할거고, 가능한 그 지점과 겹치는 애가 많게 쏴야합니다.

하지만, 선택한 타겟의 시작지점에서 끝 지점까지의 구간 중 겹치는게 아무리 많더라도, 겹치는 타겟의 구간이 종료되면 같이 거기서 타겟을 쏴야합니다.

왜냐면, 시작 지점으로 정렬을 했기 때문에, 겹쳤던 타겟의 구간을 지나버리면 어차피 다시 돌아와 한번 더 쏴야하기 때문이죠

그래서 선택한 구간 사이에 있는 타겟들을 차례대로 선택하고, 동시에 선택한 구간보다 더 빨리 끝나는 애가 있으면 가능한 구간을 좁혀준다! 가 포인트가 되겠습니다.

그럼 이제 배열을 정렬을 해야 할텐데, 아직 자바에 익숙하지 않아 고생 좀 했습니다...

import java.util.*;
class Solution {
    public int solution(int[][] targets) {
        int answer = 0;
        
        Arrays.sort(targets, (el1, el2)->{
            if(el1[0] == el2[0]){
                return Integer.compare(el1[1], el2[1]);
            } else {
                return Integer.compare(el1[0], el2[0]);
            }
        });
        boolean check = true;
        int start_num = targets[0][0];
        int end_num = targets[0][1];
        if(targets.length == 1){
            answer = 1;
        }
        for(int i=1; i<targets.length; i++){
            if (check == true){              
                check = false;
            } 
                if (targets[i][0] < end_num){
                    end_num = end_num > targets[i][1] ? targets[i][1] : end_num;
                } else{
                    answer += 1;
                    start_num = targets[i][0];
                    end_num = targets[i][1];
                    check = true;
                    if(i == targets.length-1){
                        check = false;
                    }
                    
                    
                    
                }
            }
        if (check == false){
            answer++;
        }
            
        
        
        return answer;
    }
}