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

PROBLEM

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

SOLUTION

진출 지점을 기준으로 정렬한 후, 탐색하면서 진출 지점에 카메라를 설치한다. 설치된 카메라에 만나지 않으면 해당 차량의 진출 지점에 카메라를 또 설치한다. 이런식으로 반복하면 최소 개수의 카메라를 설치하면서 모든 차량을 만날 수 있다.

처음에는 하나의 카메라를 설치할 때, 최대한 많은 차량이 만나도록 설치를 하면 된다고 생각했다.

  1. 차량이 가장 많이 겹치는 구간을 찾아서 카메라를 설치한다.
  2. 카메라와 만난 차량들을 제거한다.
  3. 아직 차량이 남았다면, 1번으로 돌아간다.
  4. 그렇지 않으면 모든 차량이 만났으므로 카메라 개수를 반환한다.

이렇게 하면 해결은 가능하지만, 이 방식은 구현하는데 복잡한 것 같다고 느껴졌다.

따라서 정렬을 이용하는 방법을 선택했다. 카메라와 아직 만나지 않은 차량에 대해서, 그 차량의 진출 지점에 카메라를 설치하는 것이 이 카메라에 다른 차량들도 최대한 만날 수 있도록 하는 방법이다. 즉, 진출 지점으로 정렬되어 있다면, 순회하면서 차량의 진출 지점에 카메라를 설치하되, 이전에 설치한 카메라와 현재 차량이 만난다면 그 차량을 위한 카메라는 설치하지 않아도 된다.

SOURCE CODE (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import java.util.*;

class Solution {
  public int solution(int[][] routes) {
    int answer = 0;

    // 진출 지점을 기준으로 정렬
    Arrays.sort(routes, (o1, o2) -> {
      return Integer.compare(o1[1], o2[1]);
    });

    int cameraPos = 0;  // 카메라를 설치했던 지점
    for (int i = 0; i < routes.length; i++) {
      // 카메라를 하나도 설치하지 않았으면
      if (answer == 0) {
        cameraPos = routes[i][1];
        answer++;
        continue;
      }
      // 카메라를 설치한 지점에 만난다면
      if (routes[i][0] <= cameraPos && cameraPos <= routes[i][1]) {
        continue;
      }

      // 카메라 설치
      cameraPos = routes[i][1];
      answer++;
    }

    return answer;
  }
}

OFF THE RECORD

어떻게 이러한 방식을 도출해 냈냐고 물으면 직관적으로 떠올랐다.

댓글 남기기

관련있는 다른 게시글