[프로그래머스/greedy/level3] 단속카메라

1. 핵심 유형

• 그리디 문제

• 정렬을 통한 그리디 로직 적용하기

2. 문제 해결 전략

1. 각 차량이 고속도로를 벗어나는 지점(routes[1])을 기준으로 오름차순 정렬한다.
   (CollectionFramework에서 제공하는 정렬은 QuickSort를 사용한다.)
   

2. 차량을 확인하며 이전의 차량이 고속도로를 벗어나는 시점과 다음 차량의 고속도로를 진입하는 시점이 겹치는지를 확인한다.

   • 겹치치 않을 경우, 카메라를 배치하고 카메라를 놓을 후보위치(cameraLocation)를 업데이트한다.

3. 문제 풀고 느낀점

어제 풀었던 섬 연결하기 문제에서 아이디어를 얻어 문제를 해결했다. 시작과 끝지점이 존재할 경우, 정렬을 하고 순차적으로 조건에 따라서 문제를 해결한다.

우선 순위 큐로도 문제를 해결할 수 있지만 우선 순위 큐를 사용하는 경우는 추가되는 원소가 특정 기준에 따라 재정렬하는 경우에 우선순위 큐를 사용하는 편이라 리스틀 정렬하여 해결했다.
(아마 우선 순위큐로 문제를 풀 경우, 원소가 추가될 때마다 정렬을 해야하기 때문에 시간 초과가 발생하지 않을까 싶다.)

4. 문제 풀이 코드

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

class Solution {
    public int solution(int[][] routes) {
        List<Car> carList = new ArrayList<>();
        for (int i = 0; i < routes.length; i++) {
            carList.add(new Car(i, routes[i][0], routes[i][1]));
        }

        carList.sort(Comparator.comparingInt(Car::getEndPoint));

        int answer = 0;
        int cameraLocation = Integer.MIN_VALUE;
        for (Car car : carList) {
            if (cameraLocation >= car.getStartPoint()) {
                continue;
            }
            
            cameraLocation = car.getEndPoint();
            answer++;
        }

        return answer;
    }
}

class Car {
    private int index;
    private int startPoint;
    private int endPoint;

    public Car(int index, int startPoint, int endPoint) {
        this.index = index;
        this.startPoint = startPoint;
        this.endPoint = endPoint;
    }

    public int getIndex() {
        return index;
    }

    public int getStartPoint() {
        return startPoint;
    }

    public int getEndPoint() {
        return endPoint;
    }
}