Lv 3. 단속카메라

https://school.programmers.co.kr/learn/courses/30/lessons/42884?language=java

프로그래머스

이 문제를 푸는데에 있어 진출지점 즉 끝나는지점을 기준으로 오름차순 정렬하고 끝나는지점이 다음지점을 커버하는지 안커버하는지만 안다면 보다 쉽고 최적화된 코드를 짤 수 있음을 알게 되었다.

나는 시작지점과 끝지점을 모두 고려하여 코드를 작성했기 때문에 쓸데없는 메모리소모가 많았지만.
GPT 는 끝지점 즉 진출지점을 기준으로 다음 루트가 커버되는지 확인하여 보다 최적화된 코드를 짤 수 있었다.

Greedy란 탐욕법으로 
그때그때 최적의 해를 찾아내는 알고리즘을 의미한다.
나는 이것이 최적의 해라고 생각했는데 보다 깔끔하고 쉬운방법이 있었다.

//들어오는 route 별 
//정렬 먼저할까?
//start 지점이 낮은순 end가 높은순
//하나씩의 node를 불러오면서 만약 새로운 answer list안의 노드범위안에 들지않으면 새로운 감시카메라 생성
// 해당한다면 기존 answerlist의 노드범위를 조정

import java.util.*;

class Solution {
    class Node{
        int start;
        int end;
        public Node(int start, int end){
            this.start = start;
            this.end = end;
        }
    }
    private int check(Node n, List<Node> answer){
        for(int i = 0 ; i < answer.size() ; i++){
            if((answer.get(i).start <= n.start 
                && answer.get(i).end >= n.start) || 
               (answer.get(i).start <= n.end 
                && answer.get(i).end >= n.end))
                return i;
        }
        return -1;
    }
    public int solution(int[][] routes) {
        
        List<Node> list = new ArrayList<>();
        
        for(int[] route : routes)
            list.add(new Node(route[0],route[1]));
        
        //정렬
        Collections.sort(list,(n1,n2)->{
            if(n1.start==n2.start)
                return n2.end-n1.end;
            return n1.start - n2.start;
        });
        
        List<Node> answer = new ArrayList<>();
        for(Node n : list){
            int after = check(n,answer);
            if(after == -1)
                answer.add(n);
            else{
                answer.set(after,new Node(Math.max(answer.get(after).start,n.start),
                                         Math.min(answer.get(after).end,n.end)));
            }
        }
        return answer.size();
    }
}

// GPT의 답변

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        // 진출 지점을 기준으로 정렬
        Arrays.sort(routes, (a, b) -> Integer.compare(a[1], b[1]));
        
        int cameras = 0;
        int lastCameraPosition = Integer.MIN_VALUE;
        
        for (int[] route : routes) {
            // 현재 차량의 진입 지점이 마지막 카메라 위치를 넘어섰다면
            if (lastCameraPosition < route[0]) {
                cameras++; // 새로운 카메라 설치
                lastCameraPosition = route[1]; // 카메라 위치 갱신
            }
        }
        
        return cameras;
    }
}