단속카메라 (2021. 07. 28) Security Camera
문제 및 풀이 주소
문제 설명
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한사항
- 차량의 대수는 1대 이상 10,000대 이하입니다.
- routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
- 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
- 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.
입출력 예
| routes | return |
|---|---|
| [[-20,15], [-14,-5], [-18,-13], [-5,-3]] | 2 |
입출력 예 설명
- -5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
- -15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.
문제 해결
해당 문제는 프로그래머스 탐욕법(Greedy)에 관한 문제이니, 탐욕법이 무엇인지 먼저 찾아보았다. 탐욕법이란,
- 현재 주어진 상황에서 최고의 조건을 찾는것
- 다음 상황에서의 최고의 조건을 순차적으로 찾는다.
- 주어진 문제는 대상이 되는
컬럼을 원하는 형태의 정렬이 되어야 한다.
인데, 주어진 문제는 컬럼들의 도착시간을 기준으로 정렬을 해야한다.
해결 방안 추측
문제의 예시와는 상관없이, 정렬이 된 상태에서 순차적으로 Loop하며 대상 순서가 될때 마다 시작시간 ~ 도착시간에 포함되는 것을 체크하며, 모든 체크 배열이 완성되면 빠져나오는 것으로 하였다.
이슈 케이스
사실 처음에는 다른문제와 마찬가지로 삽질의 늪에서 빠져나올 수 없었다. 예시의 저 결과는 어째서 저렇게 나온것인가.. 에서 이해하는데 한참을 헤매버렸다.
문제 해결
각각의 풀이에 의한 설치되는 개수가 중요하다
나는 추측에 작성한대로 Loop하며 해당 시간 범위에 포함되는 모든 대상을 방문대상으로 하여 처리한다고 하였다. 즉 예제에서는 4개의 컬럼을 2개씩 잡아서 보여주었지만, 시간 범위에 들어올 수 있으면 1대의 카메라에 3개의 컬럼값이 올 수도 있는것이다. 즉, 실제 구현은 3개의 컬럼, 1개의 컬럼으로 묶었지만 결과는 설치하는 카메라의 개수만 반환하면 되므로 결과값은 동일하게 2이다.
가장 중요한 시간범위의 체크 코드는 다음과 같다
// arr1의 값을 중심으로 비교하므로 정렬의 순서가 필수적으로 중요해졌다.
private boolean isContains(int[] arr1, int[] arr2){
if(arr2[0] <= arr1[0] && arr1[0] <= arr2[1]){
// -20 <= -18 <= 15
return true;
}else if(arr2[0] <= arr1[1] && arr1[1] <= arr2[1]){
// -20 <= -13 <= 15
return true;
}
return false;
}이슈 케이스
문제를 해결해도 효율성 체크에서 시간초과가 떠버렸다. 문제의 코드는 아마 stream api를 사용하거나 Collection을 사용하는 부분일 것이다. (항상 그래왔다..)
문제 해결
최초 초기 정렬을 stream으로 표현했는데 다음과 같이 변경하였다.
// 변경 전, 효율성 테스트 미통과
int[][] sortArr = Arrays.stream(routes).sorted(Comparator.comparing(route -> route[1])).toArray(int[][]::new);
// 변경 후, 효율성 테스트 통과
Arrays.sort(routes, (o1, o2) -> {
if(o1[1] == o2[1])
return Integer.compare(o1[0], o2[0]);
else
return Integer.compare(o1[1], o2[1]);
});즉, 효율성을 같이 따지는 문제는 Stream과 Collection의 사용을 하면 안된다. (실무처럼 하기 위해 Stream을 많이사용 하고 있는데 배열만 사용해야한다니..)
테스트 결과 - 정확성
| 테스트 번호 | 통과여부 | 메모리 및 시간 |
|---|---|---|
| 테스트 1 | 통과 | (0.81ms, 52MB) |
| 테스트 2 | 통과 | (0.88ms, 54.3MB) |
| 테스트 3 | 통과 | (1.00ms, 51.5MB) |
| 테스트 4 | 통과 | (1.02ms, 53MB) |
| 테스트 5 | 통과 | (1.05ms, 53.4MB) |
테스트 결과 - 효율성
| 테스트 번호 | 통과여부 | 메모리 및 시간 |
|---|---|---|
| 테스트 1 | 통과 | (16.22ms, 52.8MB) |
| 테스트 2 | 통과 | (12.55ms, 52.8MB) |
| 테스트 3 | 통과 | (31.58ms, 56.1MB) |
| 테스트 4 | 통과 | (1.62ms, 52.5MB) |
| 테스트 5 | 통과 | (55.86ms, 56.6MB) |
후기
확실히 카카오를 하다가 다시 프로그래머스의 주제에 관련된 문제를 푸니, 먼저 해당 알고리즘을 공부하고 하니 훨씬 쉽게 접근을 할 수 있었다. 여러 알고리즘과, 여러 풀이법을 경험하고나서 카카오문제를 접하는것이 나을듯 하다..
