관리 메뉴

공부공간

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

Greedy

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

SangwonSeo 개발자가될수있을까? 2020. 8. 17. 14:24
728x90

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

 

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

[[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2

programmers.co.kr

 

 


정렬 후, 내가 Cover 할수있는 범위를 좁혀가면서 그 범위를 넘었을 시에 필요한 카메라를 증가시켜주는 

 

그리디문제이다.

 

사실 우리 머리는 그리디문제를 잘 못풀게 되어있다.


import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Solution {
    public int solution(int[][] routes) {
          int answer = 1;
	        ArrayList<int[]> al = new ArrayList<>();
	        int size = routes.length;

	        for(int i = 0 ; i < size ; i++) al.add(routes[i]);
	        Collections.sort(al, new Comparator<int[]>() {
	        	@Override
	        	public int compare(int[] o1, int[] o2) {
	        		 return o1[0]-o2[0];
	        	}
			});
	        int CoverMax =  al.get(0)[1];
	        int CoverMin =  al.get(0)[0];
	      for(int i = 1 ; i < size; i++) {
	        	if(al.get(i)[1] < CoverMax) {
	        		CoverMax = al.get(i)[1];
	        	} else if(al.get(i)[0] > CoverMax) {
	        		CoverMax = al.get(i)[1];
	        		answer++;
	        	}
	        }
	        return answer;
    }
}

 

728x90

'Greedy' 카테고리의 다른 글

프로그래머스 ) 단속카메라  (0) 2020.08.17
BOJ - 1781 ) 컵라면  (0) 2020.06.02
0 Comments
댓글쓰기 폼