문제 바로가기

문제

풀이

접근 방식

1) 나간 지점이 큰 순으로 정렬한다.
2) 한 차량씩 방문하여 같은 카메라를 사용할 수 있는가의 여부를 판단한다.

1) 나간 지점이 큰 순으로 정렬

1) 은 static class Car를 만들고, Comparable을 구현하여

• end가 큰 순대로
• end가 같다면 start가 작은 순대로

정렬되도록 하였다.

2) 카메라 설치

이제 정렬된 리스트를 차례대로 방문하며 2) 를 구현해보자.

현재 차량의 구간 start와 end가 있다. 이는 카메라를 설치할 수 있는 구간을 의미한다.

• 만약 다음 차량의 구간과 현재 구간이 겹친다면 카메라를 설치할 수 있는 구간을 업데이트 해주고,
• 전혀 겹치지 않는다면 카메라를 더 설치해야 한다는 의미이므로 cnt++ 해준 뒤, 차량 구간을 새로 업데이트 해준다.

다음 차량 next의 구간이 현재 구간 cur이 겹치는지 확인

• next.end >= cur.start 이어야 한다.
  (물론 next.end <= cur.end 의 조건도 만족시켜야 하지만, 이는 이미 1) 에서 end가 큰 순대로 정렬시킨 후 순서대로 방문하는 것이므로 언제나 만족한다.)

해당 겹치는 구간으로 구간 업데이트

• cur.start = cur.start 와 next.start 중 더 큰 것
• cur.end = next.end

(*start와 end가 구간이 좁혀지는 쪽으로 업데이트 된다.)

제출 코드

import java.util.*;

class Solution {
    static class Car implements Comparable<Car> {
        int start;
        int end;
        public Car(int start, int end) {
            this.start = start;
            this.end = end;
        }
        public int compareTo(Car car) {
            int result = car.end - this.end;
            if(result == 0) {
                result = this.start - car.start;
            }
            return result;
        }
    }
    
    public int solution(int[][] routes) {
        ArrayList<Car> carList = new ArrayList<>();
        for(int i=0; i<routes.length; i++) {
            carList.add(new Car(routes[i][0],routes[i][1]));
        }
        Collections.sort(carList);
        
        int start = carList.get(0).start;
        int end = carList.get(0).end;
        int cnt = 1;
        for(int i=1; i<carList.size(); i++) {
            Car car = carList.get(i);
            if(car.end >= start) {
                end = car.end;
                start = Math.max(car.start,start);
            } else {
                // 아예 안 겹침
                cnt ++;
                end = car.end;
                start = car.start;
            }
        }
        return cnt;
    }
}

---

이것두 몇 ~ 달 전엔 못 풀었던 문제였는데 풀었다
뿌듯해 .....