프로그래머스 - 단속카메라 (sol.java)

◎문제 링크

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

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

---

◎문제 파악

 

그리디로 풀어야 한다는 것은 알았고, 진입한 지점과 나간 지점의 차를 기준으로 정렬하여 정확성 테스트를 , 효율성 테스트에서 모두 시간 초과를 받았다. (여러 테스트 케이스를 실행해보니 정확한 알고리즘도 아니었다.)

 

이 문제의 핵심은

 

1. 카메라는 차가 빠져나가는 지점에 설치해야 한다.

2. 차가 빠져나가는 지점을 기준으로 정렬해야 한다.

이다.

 

---

예시를 보면서 문제를 파악하자

routes = [[-20,15], [-14,-5], [-18,-13], [-5,-3]]

-5 지점에 카메라를 설치하면 두 번째 네 번째 차량이 카메라를 만난다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만난다.

 

다른 카메라 설치 지점도 있을 수 있다.

예를 들어,

-13 지점에 카메라를 설치하면 첫 번째, 두 번째, 세 번째 차량이 카메라를 만난다.

-4 지점에 카메라를 설치하면 네 번째 차량이 카메라를 만난다.

 

그리디하게 생각하면, 카메라가 최대한 많은 차량을 찍을 수 있게 해야 하고, 그러므로 -13,-4에 카메라를 설치한 경우가 그리디하게 카메라를 설치한 것이다.

카메라가 최대한 많은 차량을 찍을 수 있게 하기 위해서는 최대한 차량이 고속도로를 나가는 지점에 가깝게 카메라를 설치해야 한다. 차량이 고속도로를 나가는 지점에 가깝게 카메라를 설치할수록 다음 차가 찍힐 수 있는 가능성이 높아지기 때문이다.

 

ex.

1	1	1
		2	2	2	2
			3	3
				4	4

차량 1은 0에 들어와서 2에 나간다.

차량 2는 2에 들어와서 5에 나간다.

차량 3은 3에 들어와서 4에 나간다

차량 4는 4에 들어와서 5에 나간다

 

나가는 지점이 3보다 뒤에 있는 차량 중 최대한 많은 차를 찍기 위해서는 카메라를 4에(최대한 차량이 고속도로를 나가는 지점에 가깝게) 설치해야 한다.

--> 1. 카메라는 차가 빠져나가는 지점에 설치해야 한다.

 

좀 더 깊게 생각해서, 나가는 지점이 3보다 앞선 차량도 고려해 주어야 하므로, 나가는 지점이 작은 차부터 1의 규칙을 적용하면, 모든 차량을 고려할 수 있다.

--> 2. 차가 빠져나가는 지점을 기준으로 정렬해야 한다.

---

◎코드 구현

package Programmers.SpeedTrap;

import java.util.Arrays;
import java.util.Comparator;



public class MySolution {

	public int solution(int[][] routes) {

		int answer = 0;

		//고속도로를 나간 지점을 기준으로 오름차순 정렬
		Arrays.sort(routes, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o1[1] - o2[1];
			}

		});
		
		int start = -1; //카메라를 설치한 지점의 index값
		int count = 0; //카메라에 찍힌 차의 개수
		int[] arr = {0,0}; //초기화하기 위한 변수(like null)

		while (count != routes.length) {
			int camera = 0;
			int tmp = start;

			/* 반복 횟수를 줄이기 위해서 tmp + 1부터 탐색한다.
			 *  tmp = start이고, start가 카메라를 설치한 지점의 index값이므로
			 *  tmp 이하의 값은 이미 카메라에 찍힌 차들이다.
			 */
			
			for (int i = tmp + 1; i < routes.length; i++) {
				if (start == tmp) { //카메라를 설치할 지점을 찾지 못했으면,
					if (routes[i]!=arr) { // 이미 차가 찍혀서 초기화 되어있는지 확인
											  // 초기화 되어있지 않으면
						camera = routes[i][1]; //차가 나가는 지점에 카메라 설치
						answer++;
						routes[i] = arr; //routes[i]은 카메라에 찍힌 차이므로 초기화
						count++;
						start = i;
					}
				}
				else {
					if (routes[i]!=arr) { //초기화 되어있지 않으면(차가 카메라에 찍히지 않았으면)
						
						/*
						 * routes는 이미 고속도로를 나간 지점을 기준으로 오름차순 정렬되어 있고.
						 * 카메라를 차가 나간 시점에 설치하였으므로,
						 * 들어온 지점이 카메라 설치 지점보다 작기만 하면,
						 * 차가 들어온 지점 < 카메라 < 차가 나간 지점(정렬로서 보장)
						 * 이 성립한다.
						 */
						
						if (routes[i][0] <= camera) {
							routes[i] = arr; //카메라에 차가 찍혔으므로 초기화
							count++;
						}
					}
				}

			}

		}

		return answer;

	}

	public static void main(String[] args) {
		int[][] routes = { { -20, 15 }, { -14, -5 }, { -18, -13 }, { -5, 3 } };
		// int[][] routes = { { -10, 10 }, { 9, 11 }, { 11, 17 }, { 13, 17 } };
		MySolution sol = new MySolution();
		System.out.println(sol.solution(routes));

	}
}

---

◎다른 사람의 풀이 1

package Programmers.SpeedTrap;

import java.util.Arrays;

public class Others_Solution1 {
	public int solution(int[][] routes) {
		//차량이 나가는 지점을 기준으로 정렬
        Arrays.sort(routes, (a, b) -> Integer.compare(a[1], b[1]));
        int ans = 0; //카메라 개수
        int last_camera = Integer.MIN_VALUE;
        
        for (int[] a : routes) {
        	 //마지막 카메라가 설치된 지점이 차량의 진입 지점보다 작다면 새로운 카메라를 설치해야함 
            if (last_camera < a[0]) {
                ++ans;
                //새로운 카메라는 차량이 나가는 지점에
                last_camera = a[1];
            }
        }
        return ans;
    }
}

1. 카메라는 차가 빠져나가는 지점에 설치해야 한다.

2. 차가 빠져나가는 지점을 기준으로 정렬해야 한다.

외에

3. 카메라가 설치된 지점이 차량의 진입 지점보다 작으면 카메라를 새로 설치해야 한다

는 걸 적용하여 더욱 깔끔한 코드를 만들었다.

 

문제를 파악하고 숨겨진 풀이 원리를 찾는 게 너무 어려운 것 같다...

내가 작성한 코드보다 훨씬 빠르다.

---

◎다른 사람의 풀이 2

package Programmers.SpeedTrap;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.Stack;

public class Others_Solution2 {
	 public class Car implements Comparable <Car>{
	        boolean isIn;
	        int spot;
	        int index;

	        public Car(boolean isIn, int spot, int index) {
	            this.isIn = isIn;
	            this.spot = spot;
	            this.index = index;
	        }

	        @Override
	        //차량의 들어온, 나간 시점을 기준으로 비교
	        public int compareTo(Car o) {
	            if (spot < o.spot) {
	                return -1;
	            }
	            else if (spot > o.spot) {
	                return +1;
	            }
	            else {
	                return 0;
	            }
	        }
	    }

	    public int solution(int[][] routes) {
	        int answer = 0;
	        int n = routes.length;
	        ArrayList<Car> list = new ArrayList<>();

	        for (int i = 0; i < n; i++) {
	            list.add(new Car(true, routes[i][0], i)); //들어옴, 들어온 지점, 차량 번호
	            list.add(new Car(false, routes[i][1], i)); //나감, 나간 지점, 차량 번호
	        }
	        Collections.sort(list);

	        //차량이 카메라에 찍혔는지 검사하는 배열
	        boolean[] handled = new boolean[n];
	        Stack<Car> stack = new Stack<>();

	        Iterator<Car> iterator = list.iterator();
	        while(iterator.hasNext()) {
	            Car car = iterator.next();
	            
	            //들어온 차들을 모두 stack에 저장
	            if (car.isIn) {
	                stack.push(car);
	            }
	            else {
	            	//카메라에 안찍힌 차가 나가면,
	                if (!handled[car.index]) {
	                	//카메라를 차가 빠져나가는 지점에 설치하므로,
	                	// stack에 저장된 차들은 아직 고속도로를 달리고 있는 차
	                	// = 카메라에 찍히는 차들
	                    while(!stack.isEmpty()) {
	                        handled[stack.pop().index] = true;
	                    }
	                    answer++;
	                }
	            }
	        }

	        return answer;
	    }
}

car 클래스를 구현해서 풀었다는 게 재미있는 풀이었다.

풀이 알고리즘은 위의 풀이와 같이

1. 카메라는 차가 빠져나가는 지점에 설치해야 한다.

2. 차가 빠져나가는 지점을 기준으로 정렬해야 한다.

3. 카메라가 설치된 지점이 차량의 진입 지점보다 작으면 카메라를 새로 설치해야 한다

를 적용하여 작성되었다.

---

무엇을 그리디 하게 생각해야 하는지, 문제의 원리를 살피기 위해선 어떻게 해야 하는지 고민하고, 문제를 푸는 것만이 아닌 효율적인 코드를 만들기 위해 노력해야 한다는 걸 느끼게 된 문제였다.

 

git 코드:

https://github.com/jerry-ryu/java_problemsolving_algorithm/tree/main/%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/Programmers_SpeddTrap%2C21.05.26

jerry-ryu/java_problemsolving_algorithm