프로그래머스 단속카메라(자바) - 그리디

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

routesreturn

[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]

2

 

 

-틀린 코드

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        int start = 0; //현재 카메라 위치
        int end = 0;
        Arrays.sort(routes, (o1, o2) -> Integer.compare(o1[1], o2[1]));
        for (int i = 1; i < routes.length; i++) {
            answer++;
            if (routes[i][0] <= routes[i-1][1]) { //카메라 설치 필요x
                start = routes[i][0];  //겹치는 부분의 제일 첫 부분에 카메라 설치
                end = routes[i-1][1];
                i++;
                while(i < routes.length) {
                    if (routes[i][0] >= start && routes[i][0] <= end) {
                        i++;
                        start = routes[i][0];
                    }
                    else break;
                }
            }
        }
        return answer;
    }
}

처음에는 겹치는 부분을 생각하고, 그 사이에 다음 구간이 있는 경우 넘어가고 아닌 경우 answer을 플러스 해주는 방식으로 복잡하게 생각했다. 

그런데 생각보다 간단하게 풀 수 있었다.

1. routes를 각 구간의 진출점을 기준으로 정렬해준다.

2. min 값을 가장 작은 수로 설정한다.(구간의 시작점이 마이너스도 가능하므로 MIN_VALUE 사용해야 함.)

3-1. 그 다음 구간의 시작점이 min값보다 작으면 겹치는 것이므로 카메라를 추가해주지 않고 그 다음 구간의 시작점과 min 값을 비교한다. 

3-2. 만약 다음 구간(x 구간)의 시작점이 min값보다 크다면 겹치지 않는 것이므로 카메라를 추가해주고 min값을 x 구간의 진출점을 min값으로 설정해준다.

이 과정을 routes의 길이만큼 반복해주면 된다.

 

 

-정답 코드

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        Arrays.sort(routes, (o1, o2) -> Integer.compare(o1[1], o2[1]));
        int min = Integer.MIN_VALUE;
        for (int[] route : routes) {
            if (min < route[0]) {   //안 겹치는 경우
                answer++;
                min = route[1];
            }
        }
        return answer;
    }
}