[프로그래머스] Java 단속카메라

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

차량들의 진입점과 출구점이 주어졌을 때, 각 차량들이 겹치지 않도록 선택하는 것은 최대한 적은 공간을 차지하면서 차량들을 배치하는 문제입니다. 이를 해결하기 위해서는 먼저 고속도로를 나간 지점이 빠른 차량을 우선적으로 선택하는 것이 중요합니다.

소스코드

import java.util.*;

class Solution {
    static class Car implements Comparable<Car> {
        int src, desc;
        public Car(int src, int desc) {
            this.src = src;
            this.desc = desc;
        }
        
        @Override
        public int compareTo(Car c) {
            return this.desc - c.desc;
        }
    }
    
    public int solution(int[][] routes) {
        List<Car> cars = new ArrayList<>();
        for(int[] route: routes) {
            Car newCar = new Car(route[0], route[1]);
            cars.add(newCar);
        }
        
        Collections.sort(cars);
        
        int answer = 0;
        int last = -1;
        for(Car cur: cars) {
            if(last == -1) {
                last = cur.desc;
                answer++;
            } else if (cur.src <= last && cur.desc >= last) {
            } else {
                last = cur.desc;
                answer++;
            }
        }
        
        return answer++;
    }
}

코드 설명

• Car 클래스
  Car 클래스는 각 차량의 진입 구간(src)과 출구 구간(desc)을 나타냅니다.
  • 이 클래스는 Comparable<Car>를 구현하여 Car 객체들을 desc (출구 구간) 기준으로 오름차순 정렬하도록 정의됩니다.
  • compareTo 메서드는 출구 구간 desc 값 기준으로 비교하여 정렬 순서를 결정합니다.
• Car 객체 생성 및 리스트에 추가:
  • routes 배열을 순회하여 Car 객체를 생성하고, 각 차의 진입점(src)과 출구점(desc)을 Car 객체에 저장한 후 cars 리스트에 추가합니다.
• 정렬:
  • cars 리스트를 desc 값(출구 지점)을 기준으로 오름차순 정렬합니다.
  • 정렬 기준이 desc 값이므로, 먼저 출구가 빠른 차량부터 선택하게 됩니다. 이는 그리디 알고리즘에서 가장 중요한 부분입니다.
• 차량 선택:
  • 차량을 하나씩 순차적으로 살펴보면서, 겹치지 않도록 선택합니다.
  • last는 마지막으로 선택된 차량의 출구점을 추적하는 변수입니다. 처음에는 -1로 초기화합니다.
  • for문을 통해 각 차량의 구간을 확인하면서, 다음 조건에 맞는 차량만 선택합니다:
    • last == -1: 첫 번째 차량이므로 last를 그 차량의 출구점으로 설정하고 차량을 선택합니다.
    • cur.src <= last && cur.desc >= last: 현재 차량의 진입점이 last보다 작거나 같고, 출구점이 last보다 크거나 같은 경우는 이미 다른 차량이 선택된 구간과 겹친다는 의미입니다. 이 경우에는 차량을 선택하지 않고 넘어갑니다.
    • 그렇지 않으면, 현재 차량을 선택하고, last를 해당 차량의 출구점(desc)으로 갱신합니다.
• 결과 반환:
  • 최종적으로 선택된 차량의 수는 answer 변수에 저장됩니다.
  • 마지막에 answer++는 answer를 증가시키는 부분인데, 이 부분은 잘못된 코드입니다. return answer로 해야 합니다. answer++는 잘못된 값이 반환될 수 있습니다.