[프로그래머스] 42884. 단속 카메라

문제 링크

[프로그래머스] 42884. 단속 카메라

풀이 과정

예를 들어, 위와 같이 차량 두 대에 대한 고속도로 이용 정보가 주어졌다고 생각해봅시다.

왼쪽 예시에서는 첫 차량이 고속도로를 나가기 전에, 두 번째 차량이 고속도로를 진입합니다. 그렇게 되면, 빨간색 빗금과 같이 겹치는 부분이 생기게 됩니다. 이 빗금은 이전 차량이 고속도로를 빠져나가기 전에 다음 차량이 고속도로에 진입했음을 의미합니다.

하지만, 오른쪽 예시에서는 첫 차량이 나간 후에 두 번째 차량이 고속도로에 들어오게 되므로, 추가적인 카메라 설치가 필요합니다.

위 간단한 예시를 통해서 카메라 설치 대수는 이전 차량의 진출 지점과 다음 차량의 진입 지점과 관련있다는 것을 알 수 있습니다.

let answer = 1;
routes.sort((a, b) => a[0] - b[0]);
let prevEnd = routes[0][1];

로직 수행 전 다음과 같은 초기화 과정을 진행합니다.

• 먼저, 변수 answer에 맨 처음 차량 단속을 위한 카메라 1을 설정합니다.
• 차량의 고속도로 진입, 진출 정보를 나타내는 배열 routes 를 진입 지점 오름차순으로 정렬합니다.
• 이전 차량의 진출 지점을 나타내는 변수 prevEnd 를, 정렬된 배열 routes 의 맨 처음 차량의 진출 지점( routes[0][1] )으로 설정합니다.

for (let now in routes) {
  let start = routes[now][0],
    end = routes[now][1];

  if (start > prevEnd) {
    answer++;
    prevEnd = end;
  }

  if (end < prevEnd) {
    prevEnd = end;
  }
}

모든 차량의 고속도로 진입, 진출 정보를 순회하며, 다음과 같은 과정을 거칩니다.

• 이전 차량이 빠져나가고 다음 차량이 들어오면, 겹치는 부분이 없으므로 추가적인 카메라가 필요합니다. 따라서, answer 를 증가시킨 뒤, prevEnd 만 현재 차량의 진출 지점으로 설정해줍니다.
• 이전 차량이 빠져나가기 전에 다음 차량이 빠져나가면, 완전히 겹치게 되므로, 추가적인 카메라가 필요 없습니다. 따라서, prevEnd 만 현재 차량의 진출 지점으로 설정해줍니다.
• prevEnd 를 갱신하는 작업은, 다음 번 차량이 들어옴으로 카메라를 늘려야되는 지 확인하기 위해 필요합니다.

코드

function solution(routes) {
  let answer = 1;
  routes.sort((a, b) => a[0] - b[0]);
  let prevEnd = routes[0][1];

  for (let now in routes) {
    let start = routes[now][0],
      end = routes[now][1];

    if (start > prevEnd) {
      answer++;
      prevEnd = end;
    }

    if (end < prevEnd) {
      prevEnd = end;
    }
  }

  return answer;
}

solution([
  [-20, 15],
  [-14, -5],
  [-18, -13],
  [-5, -3],
]);
solution([
  [2, 3],
  [1, 6],
  [4, 5],
]);
solution([
  [4, 6],
  [1, 3],
  [2, 5],
]);
solution([
  [3, 4],
  [1, 2],
  [5, 6],
]);
solution([
  [1, 2],
  [3, 8],
  [4, 6],
  [5, 7],
]);
solution([
  [1, 3],
  [2, 5],
  [4, 8],
  [6, 7],
]);