[프로그래머스] 단속카메라

프로그래머스 level 3 단속카메라

 

소요시간 1시간..

이것저것 생각해보고 코드를 바꿔본다고 시간이 오래걸렸다 ㅎ

 

 

1. 차량이 나간 지점 오름차순으로 routes를 정렬한다.

2. route 를 카메라를 차량이 나간 지점에 둔다.

3. 카메라 둔 위치에 다른 route들도 포함되는지 확인 후 포함되면 true 시켜준다.

4. for 문을 돌면서 카메라 둔 곳에 포함되지 않는(false) route에 다시 카메라 두고 반복!

 

public int solution(int[][] routes) {
  Arrays.sort(routes, new Comparator<int[]>() {
    @Override
    public int compare(int[] o1, int[] o2) {
    	return o1[1]-o2[1];
    }
  });

  int answer = 0;
  int N = routes.length;
  boolean[] camera = new boolean[N];
  for (int i = 0; i < N; i++) {
    if(camera[i]) continue;

    camera[i] = true;
    int pos = routes[i][1];
    answer++;

    for (int j = i+1; j < N; j++) {
      if(routes[j][0] <= pos && pos <= routes[j][1]) {
      	camera[j] = true;
      }
    }
  }

  return answer;
}