단속 카메라(프로그래머스)

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

프로그래머스

 

요구사항 분석

1. 차량의 진입 시점과 나간 시점이 주어진다.

2. 모든 차량이 한 번쯤은 찍히도록 카메라를 설치

3. 이때, 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난 것으로 간주.

4. -30000 <= routes[i] <= 30000

 

사고의 흐름

보자마자, 차가 겹치는 구간을 찾아야 한다고 생각. 그리디 알고리즘임을 바로 떠올림.

즉, 나가는 시점을 기준으로 오름차순 정렬 후 나가는 시점에 cctv를 설치하는 것.

나가는 시점을 기준으로 오름차순 정렬하면, 진입 시점만 확인하면, 겹치는지 안 겹치는지 알 수 있다.

진입시점을 확인하여 겹치면 continue; 안 겹치면, 새로운 카메라 생성 후 cnt++

비교적 쉬운 문제이다.

 

코드

import java.util.*;

class Solution {
    private Queue<int[]> queue = new PriorityQueue<>((o1, o2) -> o1[1] - o2[1]);

    public int solution(int[][] routes) {
        setRoutes(routes);
        int answer = getAnswer();
        return answer;
    }
    public void setRoutes(int[][] routes) {
        for (int i = 0; i < routes.length; i++) {
            if (routes[i][0] < routes[i][1]) {
                queue.add(new int[] { routes[i][0], routes[i][1] });
            } else {
                queue.add(new int[] { routes[i][1], routes[i][0] });
            }
        }
    }
    public int getAnswer() {
        int cnt = 0;
        int camera = Integer.MIN_VALUE;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            if (camera < current[0]) {
                camera = current[1];
                cnt++;
            }
        }
        return cnt;
    }
}