[프로그래머스] 42884 단속카메라

1. 문제

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

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

2. 접근방법

프로그래머스 그리디 마지막 문제

1. 나가는 위치 순으로 정렬

2. 마지막 설치 지점을 저장할 변수하나 선언 후 최소값 -30001로 저장

3. 앞에서부터 순서대로 꺼내면서

3-1. 마지막 설치지점보다 시작지점이 뒤라면 나가는 지점에 카메라 설치

3-2. 마지막 설치지점보다 시작지점이 앞이라면 이미 앞의 카메라로 단속이 가능하므로 continue

4. 설치한 카메라 수 return

 

3. 자바 코드

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

public class Solution {
	
    public int solution(int[][] routes) {
        int answer = 0;
        int nowPlace = -30001;
        
        Arrays.sort(routes,new Comparator<int []>() {
        	@Override
        	public int compare(int[] o1, int[] o2) {
        		return o1[1] - o2[1];
        	}
		});
        //도착지점 앞인 얘 하나 꺼내고
        //현재 위치보다 시작이 앞서 있으면 버리고
        //시작이 뒤면 현재 위치를 이 녀석의 도착지점으로 바꾸기
        for(int i = 0 ; i < routes.length; i++) {
        	int [] now = routes[i];
        	if(now[0] <= nowPlace)
        		continue;
        	answer++;
        	nowPlace = now[1];
        }
        return answer;
    }
}

4. 마치며

그리디 문제가 확실히 방법도출을 위해 고민을 많이 하니 재미는 있는 것 같다.