프로그래머스 단속카메라 JAVA (탐욕법, Greedy)

1. 문제

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

코딩테스트 연습 - 단속카메라

 

2. 설명

탐욕법관련된 문제다.

첫번째 배열로 정렬하고, 차량 진출지점을 기준으로 카메라 위치를 선정해 나갔다.

겹쳐지지 않는 부분이면 카메라를 한대 추가하고, 그 차량의 진출지점에 다시 카메라를 설치했다.

기본적으로 한 대 이상의 카메라가 설치되어야 되기 때문에 answer의 기본값을 1로 잡고 시작했다.

 

3. 코드

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        int answer = 1;
        Arrays.sort(routes, (n1,n2) -> {
            return n1[0]-n2[0];
        });
        int camera = routes[0][1];
        for(int i=0; i<routes.length; i++) {
            if(routes[i][0] <= camera) { // 이 부분
                if(routes[i][1] < camera)
                    camera = routes[i][1];    
            } else {
                camera = routes[i][1];
                answer++;
            }
        }
        
        return answer;
    }
}

주석달아 놓은 부분은 이미 routes를 첫번째 배열로 정렬했기 때문에 필요없는 부분이다.

따라서 요로콤 고쳤다.

import java.util.*;
class Solution {
    public int solution(int[][] routes) {
        int answer = 1;
        Arrays.sort(routes, (n1,n2) -> {
            return n1[0]-n2[0];
        });
        int camera = routes[0][1];
        for(int i=0; i<routes.length; i++) {
            if(routes[i][1] < camera)
                camera = routes[i][1];    
            if(routes[i][0] > camera) {
                camera = routes[i][1];
                answer++;
            }
        }
        return answer;
    }
}