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

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

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

풀이과정

1. 주어진 자동차 정보(출입지점, 이탈지점)을 이탈지점을 기준으로 오름차순으로 정렬한다. (단, 여기서 모든 차량은 한 방향으로만 진행한다는 가정이 있어야 한다.)
2. 맨 앞 차량(가장 먼저 이탈하는 차량)이 카메라에 잡히기 위해서는 반드시 이 차량의 [진입 지점, 이탈 지점]의 범위 내에 단속 카메라가 설치되어야 한다. 여기서 가장 다른 차량과 동선이 겹칠 가능성이 높은 지점은 이 차량의 이탈지점이다. 그 이유는 이미 1에서 이탈지점을 기준으로 오름차순 정렬되어있기 때문이다. 

1. 맨 앞 차량의 이탈지점에 단속 카메라를 설치한다고 했을 때, 이 단속 카메라에 걸리는 자동차들을 모두 리스트에서 제거한다. 그리고 단속 카메라 카운트를 1 올린다.
2. 단속 카메라에 잡히지 않는 자동차가 모두 없어질 때 까지 2, 3을 반복하고 최종 단속 카메라 카운트 결과를 반환한다.

 

소스코드

import java.util.*;

class Solution {
    public int solution(int[][] routes) {
        int counter = 0;
        Arrays.sort(routes, Comparator.comparingInt(a -> a[1]));

        Queue<Car> cars = new LinkedList<>();
        for (int[] route : routes) {
            cars.offer(new Car(route[0], route[1]));
        }

        while (!cars.isEmpty()) {
            int cameraPos = cars.poll().getTo();
            counter++;

            int size = cars.size();
            for (int i = 0; i < size; i++) {
                if (cars.peek().isDetectedAt(cameraPos)) {
                    cars.poll();
                } else {
                    break;
                }
            }
        }

        return counter;
    }
}

class Car {
    private int from;
    private int to;

    Car(int from, int to) {
    	// 한 방향 진행을 가정
        this.from = Math.min(from, to);
        this.to = Math.max(from, to);
    }

    public int getTo() {
        return to;
    }

    public boolean isDetectedAt(int pos) {
        return from <= pos && pos <= to;
    }
}

 

Comment

Greeey 알고리즘을 적용하기 위한 기준으로 무엇을 설정해야 할 지 감을 잡는것이 조금 오래 걸렸던 것 같다.

입출력 예 설명 부분을 잘 읽고 -5, -15지점에 카메라를 설치하는 것을 왜 예로 들었는지 잘 생각 해 보았다면, 문제를 읽은 직후에 단순하게 떠오르는 '가장 많은 자동차가 통과하는 지점'을 찾아가며 카메라를 설치해보는 삽질을 덜 할수 있었을 것 같다.