Today I Learned

오늘은 프로그래머스 lv.3 문제 중 랜덤한 문제를 풀어봤다. 그리디 알고리즘을 써서 문제를 해결했다.

단속카메라

https://school.programmers.co.kr/learn/courses/30/lessons/42884

문제

고속도로를 지나가는 모든 차량들이 적어도 한번은 단속카메라를 만나게 하려고 한다.
-3만~3만 범위에서 {차량의 진입지점, 나가는 지점} 으로 이차원 정수 배열 routes가 주어질 때 최소한의 카메라 대수를 구하라.

구현 과정

1. 우선 순서 없이 나열된 이차원 배열을 인덱스 1번 즉, 출구를 기준으로 오름차순으로 정렬했다.
   Arrays.sort(routes, (a,b) -> Integer.compare(a[1], b[1]))
   정렬 메서드에 람다를 이용해 a,b를 a[1], b[1]값과 비교하게 해 정렬하도록 했다.

2. 기본 아이디어는 이전 차량의 출구에 카메라를 설치한다고 가정하고 min으로 설정한다.
   다음 차량의 입구랑 비교했을 때 min값보다 작으면 카메라에 걸리니 넘어간다.

3. 하지만 min보다 다음차량의 입구 값이 크면 카메라에 안걸리니 카메라를 하나 더 만들어야 한다. min값을 해당 차량의 출구로 재설정하고 answer를 1씩 늘린다.

4. 어차피 배열은 차량들의 출구값을 기준으로 정렬되어 있으므로 그 순간의 답을 하나씩 늘려 그리디 알고리즘으로 전체 카메라의 대수를 구해도 문제가 없다. 최종적으로 answer를 반환 하면 문제없이 풀린다.

구현 코드

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        Arrays.sort(routes, (a,b) -> Integer.compare(a[1], b[1]));
        int answer = 0;
        int min = -30000;
        
        for(int[] r : routes){
            int start = r[0];
            int end = r[1];
            
            if(start>min){
                answer++;
                min = end;
            }
        }
        
        return answer;
    }
}