[알고리즘] 프로그래머스 단속카메라 (java) -그리디(greedy)-

https://programmers.co.kr/learn/courses/30/lessons/42884?language=java

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

 

프로그래머스 LEVEL3 의 단속카메라 문제를 풀어봤습니다. ㅎㅎ

 

풀이 방법은 다음과 같습니다. 

1. 종착지점을 기준으로 오름차순 정렬합니다.

2. 반복문을 통해 routes를 갖고옵니다.

3. 카메라 설치 지점과 현재 route의 진입 지점과 비교하여 카메라 설치 지점에 커버되는 곳이면 PASS 아닌 경우는 

카메라 설치 지점을 현재 route 의 종착 지점으로 변경해주고 카메라 설치 개수가 한개 늘어납니다.

 

 

풀이는 다음과 같습니다.

[Java]

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

class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solution(new int[][]{{-20, 15}, {-14, -5}, {-18, -13}, {-5, -3}});
    }

    public int solution(int[][] routes) {
        int answer = 0;
        Arrays.sort(routes, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        int min = -30001;
        for (int i = 0; i < routes.length; i++) {
            if(routes[i][0] > min){
                answer++;
                min = routes[i][1];
            }
        }

        return answer;
    }
}

 

 

https://github.com/mtjin/algorithm_practice/tree/master/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4%20%EB%8B%A8%EC%86%8D%EC%B9%B4%EB%A9%94%EB%9D%BC%20-%EA%B7%B8%EB%A6%AC%EB%94%94(greedy)-

mtjin/algorithm_practice

 

댓글과 공감은 큰 힘이 됩니다. 감사합니다.