[ 알고리즘 ] 코딩 - Programmers - 단속카메라.java

문제 링크

---

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

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

---

* Programmers - Level 3 - 탐욕 법(Greedy) - (자바) 단속카메라. java

입출력예시

 

---

사용한 로직!

* 진입구간과 진출구간을 기준으로 차량을 모두 나누어 생각

* 진입구간을 내림차순 정렬. (정렬은 유선 순위 큐(PriorityQueue를 이용)

* 현재 설치된 카메라가 구간 안에 없다면 진입하는 위치에 설치

* 현재 설치된 카메라가 구간안에 있다면 다음 자동차로 넘어감

* 지금 설치하는 카메라의 위치가 최선의 위치라 믿고 넘어가는 탐욕 법(Greedy)

---

import java.util.Comparator;
import java.util.PriorityQueue;
class Solution {
    public int solution(int[][] routes) {
        PriorityQueue<int[]> pQueue = new PriorityQueue<int[]>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return -Integer.compare(o1[0], o2[0]);
			}
		});
		
		for(int i = 0; i < routes.length; i++) {
			pQueue.offer(routes[i]); // 내림차순 정렬
		}
		
		int cctvCnt = 0;
		int cctvPos = 30001; // 초기 카메라의 위치는 가장 끝
		
		while(!pQueue.isEmpty()) {
			int[] curCar = pQueue.poll();
			if(cctvPos > curCar[0]) { // 진입구간보다 뒤에 있다
				if(cctvPos <= curCar[1]) continue; // 하지만 구간안에 있으면 pass
				cctvPos = curCar[0]; // 현재 자동차 구간보다 뒤에 있다면 카메라 위치 앞으로
				cctvCnt++;
			}
		}
        return cctvCnt;
    }
}