[프로그래머스] (Java) 단속카메라 (그리디/Greedy)

 

 

📑 1. 문제설명

---

💡 2. 접근방식

입출력 예로 주어진 route 배열을 막대그래프로 그려 봤다. 
 

최소한의 카메라를 배치해야 하므로 구간 종료 위치를 기준으로 오름차순 정렬

 
차량이 구간에서 카메라를 단 한 번만이라도 만나면 됨
종료 지점에서 다음 구간과 겹치게 되므로 최소한의 카메라를 배치가능

카메라 배치는 도로의 가장 왼쪽 끝부터 탐색하며 시작된다.
입출력 예시에서 MIN_VALUE인 -20 지점부터 오른쪽으로 가며 종료구간과 시작구간이 겹치는 부분에 카메라가 배치된다.

구간 중 가장 처음으로 만나는 종료 위치는 -15이다.
따라서 이 위치에 첫 번째 카메라를 설치한다. 
그리고 -13지점에서 현재 구간과 다음 구간이 만나지만 이미 해당 구간에는 카메라가 설치 완료 되었으므로 스킵한다. 
그리고 다음 구간인 [-14, -5]와 [-5, -3]이 겹치는 구간에 두번째 카메라를 설치한다.  

---

⭐ 3. 정답코드

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        // 카메라를 설치한 횟수 (나중에 리턴할값)
        int cameraCount = 0;
        
        // 이동 경로 종료 지점 기준으로 오름차순 정렬
        Arrays.sort(routes, new Comparator<int[]>() {
            @Override
            public int compare(int[] route1, int[] route2) {
                // 두 경로의 끝 지점(route[1])을 비교하여 오름차순으로 정렬하기
                return route1[1] - route2[1];
            }
        });
        
        // 설치된 카메라가 지나갈 수 있는 가장 끝 지점
        int lastCameraPosition = Integer.MIN_VALUE;
        
        // 모든 차량의 경로를 돌면서 카메라가 필요한 구간을 찾기
        for (int[] route : routes) {
            // 현재 차량의 시작 지점(route[0])이 기존 카메라의 끝 지점(lastCameraPosition)보다 뒤쪽이면 카메라가 필요
            if (lastCameraPosition < route[0]) {
                // 카메라 설치
                lastCameraPosition = route[1];
                cameraCount++;  // 카메라 설치 횟수 증가
            }
        }
        
        // 설치한 카메라의 개수 반환
        return cameraCount;
    }
}

 

👏🏻 좋아요 가장 많이 받은 코드

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int solution(int[][] routes) {
        Arrays.sort(routes, (a, b) -> Integer.compare(a[1], b[1]));
        int ans = 0;
        int last_camera = Integer.MIN_VALUE;
        for (int[] a : routes) {
            if (last_camera < a[0]) {
                ++ans;
                last_camera = a[1];
            }
        }
        return ans;
    }
}

---

🐦 4. 같은 유형 문제

[프로그래머스] (Java) 체육복 (그리디/Greedy)

[프로그래머스] (Java) 조이스틱 (그리디)

[프로그래머스] (Java) 큰 수 만들기 (그리디/Greedy)

[프로그래머스] (Java) 구명보트 (그리디/Greedy)