LV3 - 단속 카메라 (Java)

 

---

 

문제

 

https://school.programmers.co.kr/learn/courses/30/lessons/42884?language=java

프로그래머스

 

풀이

이 문제의 핵심은 자동차의 진출 지점을 기준으로 오름차순 하는것이다.

 

Case 1.

 

[1]   | ---------------------- | 

[2]          | ----------------------|

[3]                                  | --------------- |

 

눈으로 봤을 때 위 문제의 답은 2임을 알 수 있다.

 

우선 첫번째 차량을 위해 카메라가 한 대 필요하다.

그 다음에 차량이 첫번째 차량을 위한 카메라에 속하는지는 어떻게 알까?

다음에 들어오는 차량의 진입점이 이전 차량의 진출점과 작거나 같은지 확인하면 된다.

만약 포함되어 있으면 그 카메라의 진입, 진출 기준값으로 비교를 계속 하면 되고, 그게 아니라면 새로운 카메라를 설치해주면 된다.

진출점을 기준으로 정렬하면 새로 진입하는 차량의 진출점은 어차피 이전 차량의 진출점보다 늦게 된다. 그렇기 때문에 앞선 카메라에 속하는지 보기 위해서는 카메라 세팅시 진출점만 비교해주면 된다.

 

 

Case 2.

 

 

[1]     | ----------- |

[2]                         | ------------ |

[3]  | -------------------------------------- |

 

위 경우도 마찬가지이다.

 

첫번째 차량이 진입할 때 카메라를 설치한다.

 

두번째 차량이 진입 시점이 첫번째 차량의 진출점 보다 늦기에 새로운 카메라를 추가해준다.

마지막 차량의 진입 시점은 두번째 차량의 진출점보다 작거나 같기에 카메라를 추가해줄 필요 없다.

 

코드

import java.util.*;

class Solution {
    
    static class Car {
        public int start;
        public int end;
        
        public Car(int start, int end){
            this.start = start;
            this.end = end;
        }
    }
    
    public int solution(int[][] routes) {
        int answer = 0;
        
        List<Car> list = new ArrayList<>();
        for(int i=0; i<routes.length; i++){
            list.add(new Car(routes[i][0], routes[i][1]));
        }
        
        // 끝을 기준으로 오름차순 한다.
        list.sort((o1, o2) -> o1.end - o2.end);
        
        // 초기값
        Car reference = list.get(0);
        answer = 1;
        
        for(int i=1; i<list.size(); i++){
            Car target = list.get(i);
            
            if(target.start <= reference.end) {
                continue;
            }
            answer += 1;
            reference = target;
        }
        
        return answer;
    }
}

 

후기

 

LV3을 풀이 높은순으로 풀었는데 상위 부분 LV3급의 복잡함이 없는거 같긴하다...