[문제풀이] 단속카메라

업데이트:

문제 링크 : 단속카메라

풀이 시간 : 20분

1. 문제 풀이

모든 차량을 단속할 수 있는 카메라 최소 설치 개수를 구하는 문제

1) 리스트에 나간 지점 순으로 저장(같으면 들어온 지점 순으로)

2) 리스트에서 첫번째 차량 선택

3) 현재 카메라보다 들어온 지점이 오른쪽인지 판단

3-1) 오른쪽일 경우, 현재 카메라 위치를 그 차량의 나간 지점으로 변경 및 카메라 수 증가

4) 리스트가 빌 경우 종료, 아닐 경우 2번으로 이동

2. 소스 코드

    public int solution(int[][] routes) {
        // 가장 왼쪽에 있는 나간 지점 순으로 정렬 후 같으면 가장 왼쪽에 있는 들어온 지점순으로 정렬
        PriorityQueue<Car> pq = new PriorityQueue<>(new Comparator<Car>() {

			@Override
			public int compare(Car o1, Car o2) {
				if(o1.end<o2.end) {
					return o1.end-o2.end;
				}else if(o1.end==o2.end) {
					return o1.start-o2.start;
				}else {
					return o1.end-o2.end;
				}
			}
		});
        for (int i = 0; i < routes.length; i++) {
			pq.add(new Car(routes[i][0],routes[i][1]));
		}
        // 가장 왼쪽에 있는 나간 지점에 카메라 설치
        int pivot = pq.poll().end;
        int answer = 1;
        while(!pq.isEmpty()) {
        	Car car = pq.poll();
        	// 현재 설치된 카메라 중 가장 오른쪽에 있는 지점보다 더 오른쪽 지점에서 들어 차량 검색
        	if(car.start>pivot) {
        		// 그 차량의 나간 지점에 카메라 설치
        		pivot= car.end;
        		answer++;
        	}
        }
        return answer;
    }
	class Car{
		int start;
		int end;
		Car(int start,int end){
			this.start= start;
			this.end=end;
		}
	}

3. 후기

드디어 프로그래머스 level 2를 한 문제 빼고 다 풀었다.

블로그에는 level 2문제 풀이를 잘 올리지 않기 때문에 모를 수 도 있겠지만

드디어 본격적으로 level 3 문제를 풀게 되었다.

참고