프로그래머스 - 단속카메라

leehyunjon·2022년 11월 2일

그리디 프로그래머스

Algorithm

목록 보기

118/162

단속카메라 : https://school.programmers.co.kr/learn/courses/30/lessons/42884#

Problem

Solve

차량의 진입 지점과 진출 지점을 비교해서 최소의 단속카메라로 모든 차량을 찍을 수 있도록 구현하는 문제.

차량의 중복 지점을 찾기 위해 고민하다가 정렬을 사용해서 차량들의 중복 지점을 구하도록 접근하였습니다.

첫번째 풀이 (오답)

처음에는 진입 지점을 기준으로 오름차순 정렬하고 각 차량의 진출지점을 기준으로 카메라를 설치하고 다음 차량들의 진입 지점을 비교합니다.

다음 차량의 진입 지점이 현재 카메라 위치보다 작다면 중복되는 지점으로 놓고 다음 차량 비교합니다.
위치가 크다면 중복되지 않음으로 놓고 해당 차량의 진출 지점을 카메라 설치 지점으로 설치하고 다음 차량과 비교합니다.

routes = [[-20,-15], [-14,-5], [-18,-13], [-5,-3]] 인 경우, 정렬하여 중복 여부를 확인한다면 아래와 같습니다.

테스트케이스는 잘 넘겼지만 간과했던 사실이있었습니다.
진입 지점을 기준으로 정렬했기 때문에 진입 지점이 가장 작고, 진출 지점이 가장 큰 차량이 있다면 모든 차량이 중복으로 간주되어 하나의 카메라만 설치할 수 있게 되었습니다.

routes = [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 인 경우, 정렬하여 중복 여부를 확인한다면 아래와 같습니다.

두번째 풀이 (해결)

반대로 생각하여 차량의 진출 지점을 기준으로 오름차순 정렬을 한다면 위에 간과했던 케이스는 가장 뒤에 정렬되며 진출지점이 가장 작은 차량부터 비교하여 다음 차량을 비교하여 중복 여부를 확인 할 수 있었습니다.

Code

import java.util.Arrays;
import java.util.Comparator;
class Solution {
    public int solution(int[][] routes) {
    	//차량의 진출 지점 기준 오름차순
        Arrays.sort(routes, new Comparator<int[]>(){
            @Override
            public int compare(int[] o1, int[] o2){
                int result = o1[1]-o2[1];
                if(result == 0) result = o1[0]-o2[0];
                return result;
            }
        });
            
        int answer = 1;
        //현재 설치된 카메라 위치(차량의 진출지점)
        int cameraPos = routes[0][1];
        
        for(int i=1;i<routes.length;i++){
        	/*
            현재 카메라 위치보다 차량의 진입 지점이 더 크다면 중복되지 않음으로
            현재 카메라 위치를 차량의 진출 지점으로 갱신하고 카메라 개수를 증가시킨다.
            */
            if(cameraPos < routes[i][0]){
                cameraPos = routes[i][1];
                answer++;
            }
        }
        return answer;
    }
}