문제

링크

복습 요망!

풀이

이 문제는 풀이 방법을 떠올리지 못했다. 겹치는 접점의 개수를 이용하여 문제를 해결하려 했으나 올바르지 못한 방법이었다.

그래서 다른 사람의 풀이를 보았는데 매우 신기하고 더 열심히 해야겠다는 것을 느꼈다...

1. 진출한 시간을 기준으로 오름차순 정렬한다.

2. 처음 진출한 시간과 다음 진입한 시간을 비교한다.

3. 처음 진출한 시간 >= 다음 진입한 시간 경우 카메라를 추가로 설치할 필요가 없다.
   처음 진출한 시간 < 다음 진입한 시간 경우 카메라 1대를 추가로 설치하고 비교하는 기준값을 다음 진출한 시간으로 바꿔준다.

4. 위 과정을 반복 수행한다.

코드

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int answer = 0;

        // 진출한 시점 기준으로 오름차순 정렬
        Arrays.sort(routes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });

        int min = Integer.MIN_VALUE;
        for(int[] route : routes) {
            if (min < route[0]) {
                min = route[1];
                answer++;
            }
        }

        return answer;
    }
}

출처 : 링크
위 블로그의 설명이 많은 도움이 되었다!!