99클럽 코테 스터디 17일차 TIL - Greedy

항해99 코테 스터디 17일차 문제인 프로그래머스의 '단속카메라'는 고속도로를 지나는 모든 차량이 단속카메라를 지나가게 하기 위해 필요한 최소 카메라 개수를 구하는 문제다. 난이도는 레벨3이며 그리디 알고리즘을 통해 해결할 수 있다.

 

오늘의 문제 - 단속카메라 문제 정보

문제 키워드

- Greedy(탐욕법)

난이도

- Level 3

 

문제 요약

• 각 차량의 고속도로 진입/진출 지점이 주어진다.
• 모든 차량이 적어도 하나의 단속 카메라를 만나게 하려면 필요한 단속카메라의 최소 개수를 구하여라.

 

문제 풀이 과정  

• 고속도로를 나가는 지점을 기준으로 오름차순으로 정렬한다.
• 모든 차량에 카메라가 적어도 하나는 있어야 하므로, 현재 차량 구간에 카메라가 없다면 차량이 나가는 지점에 카메라를 추가한다.

코드

import java.util.Arrays;

class Solution {
    public int solution(int[][] routes)  {
    	// 나가는 지점 기준으로 오름차순 정렬
        Arrays.sort(routes, (o1, o2) -> {
            if (o1[1] == o2[1]) return o1[0] - o2[0];
            else return o1[1] - o2[1];
        });

		// 각 차량 구간에 카메라가 없다면 새로 추가
        int ans = 0;
        int lastCamera = -30001;
        for (int[] route : routes) {
            int in = route[0], out = route[1];
            if (in > lastCamera || lastCamera > out) {
                ans++;
                lastCamera = out;
            }
        }
        return ans;
    }
}

• 시간복잡도: O(NlogN)
• 공간복잡도: O(1)