[프로그래머스] 단속카메라 [JAVA(자바)]

‘프로그래머스 코딩테스트 고득점 Kit’ 문제 입니다. 😀

문제 👉 <코딩테스트 연습 - 단속카메라 | 프로그래머스>

1. 문제

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

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

2. 풀이

Greedy 를 이용한 문제 풀이

1. 진출 시점을 기준으로 오름차순으로 정렬
   1. 진출하려는 차량이 카메라를 한번이라도 거쳤는지 확인하기 위해
2. 카메라의 초기 위치는 -30000 으로 설정 (설치는 아님)
3. 카메라의 위치가 진입 시점 이전이라면 진출 시점에 설치

3. 코드

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        int answer = 0;
        int camera = -30000; // 카메라가 위치할 수 있는 가장 낮은 값
        // 진출 지점 오름차순 정렬
        Arrays.sort(routes, (a,b) -> Integer.compare(a[1], b[1]));

        for (int[] r : routes) {
            // 카메라가 진입 시점 이전에 위치하면 진출 시점에 설치
            if (camera < r[0]) {
                camera = r[1];
                answer++;
            }
        }

        return answer;
    }
}

---

References

---

🏋🏻 개인적으로 공부한 내용을 기록하고 있습니다.
잘못된 부분이 있다면 과감하게 지적해주세요!! 🏋