프로그래머스 Lv3 단속카메라 Java(Greedy)

문제설명

https://programmers.co.kr/learn/courses/30/lessons/42884

구현방법

• 최소한의 단속카메라를 두어 모든 차를 검문하는 방법을 찾아야한다. 가장 쉬운 방법을 생각해 보니 고속도로에서 나가는 시간을 오름차순으로 정렬하여 푸는 방법을 떠올렸다.

• 정렬한 뒤 맨 처음 나가는 차의 시간에 단속 카메라를 둔다. 즉 i번째 차의 end 이전(같은시간포함)에 들어오는 차들은 모두 이 단속카메라에 detect 할 수 있다. 이것을 반복하여 카운트하고 boolean 배열에 detect 여부를 저장하여 detect가 안되어 있는 차를 발견할 때마다 카운트를 증가시키면 된다.

코드

import java.util.*;
class Solution {
    class Car implements Comparable<Car>{
        int start;
        int end;
        Car(int start,int end){
            this.start = start;
            this.end = end;
        }
        @Override
        public int compareTo(Car o){
            if(this.end>o.end){
                return 1;
            }
            else if(this.end<o.end){
                return -1;
            }
            else{
                if(this.start>o.start){
                    return 1;
                }
                else if(this.start<o.start){
                    return -1;
                }
                else{
                    return 0;
                }
            }
        }
    }
    public int solution(int[][] routes) {
        boolean detect[] = new boolean[routes.length];
        Arrays.fill(detect, false);
        List<Car> list = new ArrayList<>();
        for(int[] t : routes){
            list.add(new Car(t[0],t[1]));
        }
        int cnt = 0;
        Collections.sort(list);
        for(int i=0;i<list.size();i++){
            if(!detect[i]){
                cnt++;
                for(int j=i;j<list.size();j++){
                    if(list.get(j).start <=list.get(i).end){
                        detect[j] = true;
                    }
                    else break;
                }
            }
        }
        return cnt;
    }
}