프로그래머스 단속카메라 자바

문제 링크

단속카메라

문제 분석

차량의 대수는 1대 이상 10,000대 이하이기 때문에 간단한 정렬 문제라고 생각했다. 정렬의 기준을 명확하게 잡으며 쉽게 풀 수 있는 문제였지만 잘못된 생각으로 기준을 잘못 잡아 틀리게 되었다. 분명 비슷한 문제도 풀었지만 아직 해당 문제를 정확하게 이해하지 못한 것 같아 기억하고자 기록을 남기게 되었습니다.

• 비슷한 문제로는 요격시스템이 있습니다.

풀이과정

1. 시간복잡도
   • 차량의 대수는 1대 이상 10,000대 이하이기 때문에 정렬(logN)을 해도 문제가 되지 않는다.
2. 정렬기준잡기
   2.1 출발점 기준으로 잡으면 어떻게 될까?
   2.2 도착점 기준으로 잡게 되면 어떻게 될까?
3. 카메라 수 구하기
   • 도착점을 end로 잡고 다음 데이터의 출발점이 end보다 작거나 같다면 같은 카메라를 사용할 수 있다
   • 다음 데이터의 출발점이 end보다 크다면 다른 카메라가 필요하다

• 2.1 출발점 기준으로 잡게 된다면?
  

• 2.2 도착점 기준으로 잡게 된다면?
  

⛳ 내가 작성한 코드

import java.util.*;
public class A단속카메라 {

	public static void main(String[] args) {
		int[][] routes = {{-20,-15}, {-14,-5}, {-18,-13}, {-5,-3}};
		
		//2.2 도착점 기준으로 정렬하기
		Arrays.sort(routes, (o1,o2)->{
			if(o1[1]==o2[1]) {
				return o1[0]-o2[0];
			}
			return o1[1]-o2[1];
		});
		
		//3. 카메라 수 구하기
		//첫 데이터의 도착점(카메라)을 end로 잡아기때문에 ans=1
		int ans=1;
		int end = routes[0][1];
		for(int i=1; i<routes.length; i++) {
			//출발지가 카메라의 위치에 벗어나 있을경우
			if(routes[i][0]>end) {
				ans +=1;
				end = routes[i][1];
			}
		}
		System.out.println(ans);
	}
}