프로그래머스[Java] - 단속카메라(Greedy)

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

코딩테스트 연습 - 단속카메라 | 프로그래머스

코드

import java.util.*;

class Solution {
   public static int solution(int[][] routes) {
		int answer = 1;
		
		// 2차원 배열 정렬 
		// 진입지점을 기준으로 오름차순 -> 같으면 나간지점을 기준으로 오름차순
		Arrays.sort(routes, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				if(o1[0] == o2[0])
					return Integer.compare(o1[1], o2[1]);
				return Integer.compare(o1[0], o2[0]);
			}
		});
		int outCome = routes[0][1];
		
		for(int i=1; i<routes.length-1; i++) {
			// 현재 차의 진출 지점이 다음에 들어올 차의 진출지점보다 클 경우
			if(outCome > routes[i][1])
				outCome = routes[i][1];
			
			// 현재 차의 진출 지점보다 다음 차의 진입 지점이 더 클경우
			// -> 단속 범위를 벗어나므로 카메라 +1 , 다음 단속범위 지정
			if(outCome < routes[i+1][0]) {
				answer ++;
				outCome = routes[i+1][1];
			}
		}
		return answer;
	}
}

풀이

그리디 문제라 그리디스럽게(?) 풀었다.

이전의 그리디 문제들도 그렇고, 범위 지정과 정렬, 하나하나 비교해가며 범위에 충족하는지 아닌지 판단하는 식으로 해결했었다. 따라서 이 문제도 비슷하게 해결한다.

먼저 주어진 2차원 배열을 정렬을하는데, 정렬 조건은 다음과 같이 했다.

 1) 차량이 고속도로에 진입한 지점순으로 오름차순 정렬을 한다.

 2) 만약 진입한 지점이 동일한 경우 ? -> 진출 지점순으로 오름차순 한다.

Comparator<T> 인터페이스를 통한 배열을 한다.

 

Comparator이란

 

위 방식대로 입출력 예를 토대로 정렬을 하면 다음과 같다.

정렬전 : [[-20,15], [-14,-5], [-18,-13], [-5,-3]] 

정렬후 : [[-20,15], [-18,-13], [-14,-5], [-5,-3]]

 

이제 고속도로에 먼저 진입한 차와 늦게 진입한 차를 비교해가며, 어디서 빠져나가는지 , 만약 빠져나갔다면 그 다음차는 카메라 단속 범위에 포함되는지 안되는지를 생각해야 한다.

 

outCome는 현재 카메라의 범위다. 초기에 카메라는 한대는 무조건 설치해야하므로 1로 설정하고, 

outCome의 초기값은 가장 첫번째로 들어온 차로 지정한다.(routes[0][1])

나가는 차(routes[i][1])의 값들과 비교해가며 더 작은 값들을 저장한다.

그 후 outCome 값보다 큰 값에서 다음 차가 출발한다면(진입지점) 단속 범위 안에 있지 않으므로, 카메라의 갯수를 +1 한다.

 

 

코드는 길지 않지만 많은 생각을 요구하는 정말 깔끔한 문제 인 것 같다..

위와 비슷한 문제들을 아래와 같다.

백준 1449번 수리공항승

프로그래머스 기지국설치