[ 프로그래머스_Lv3 ] 단속카메라 ( 그리디 - 자바스크립트 )

문제

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

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

 

How to Solve ?

 

[1] 그리디

 

문제를 어떻게 풀어야 할지에 대해서 시간 투자를 굉장히 많이 했다.

 

궁극적으로 우리가 목표로 하는 것은 최소한의 카메라를 설치 하기 위함이기에 이를 해결하는 방향으로 고민을 해보았다.

 

1-1 ) 오름차순 정렬

 

올라오는 시간이 직관적이라고 느껴져, 이를 오름차순으로 정렬하였다.

그 이유는 올라간 시간을 바탕으로 정렬을 해야, 이전의 차가 내려가는 시간과 다음의 차가 내려가는 시간을 비교 할 수 있기 때문이다.

 

1-2 ) 비교

왜 그리디일까? 혼자서 고민을 해본 결과 얻을 수 있는 결론은 "그리디"외에는 어떠한 방법으로도 접근이 어렵다. 라는 결론이 나왔다.

그리하여, 그리디답게 풀 수 있는 법을 고민을 했는데 ! 최근에 그리디 문제를 접하며 내가 결론 지었던 내용은 

 

'각 배열에 저장 되어있는 인덱스의 기준에서 최선의 일을 하는 것' 정도였다. 즉, 이번 문제의 경우에서는 각각의 자동차의 입장에서 최선의 결과를 만들기 위해 노력 하면 된다.

 

1-2-1 ) 최소한의 설치를 위한 비교

 

"최소한의 설치를 하라는 것은 불 필요한 카메라를 설치 하지 말자" 라는 말이다. 즉, 우리가 찾아야 할 것은 불 필요한 것이 언제인지 찾아 내는 것인데 ! 내가 찾았던 불 필요의 기준은 "이전의 차가 다음 차보다 늦게 나갈 때"였다.

 

이 말이 무슨 말인가 하면  '이전의 차' 라고 하는 것은 다음의 차보다 먼저 고속도로에 진입한 차를 의미한다. 만약, 이전의 차가 다음에 들어온 차보다 늦게 나간다고 가정 해본다면 다음의 차가 나가는 시점 쯤에 "1번"만 촬영하면 2대를 모두 촬영 할 수 있다.

 

즉, 다음의 차가 들어오는 시점이 이전의 차가 나가는 시점보다 느리고, 다음의 차가 나가는 시점이 이전의 차가 나가는 시점보다 빠르면 비교의 기준을 다음의 차가 나가는 기준으로 변경 하면 된다는 것이다.

 

1-2-2 ) 바로 카메라를 설치

 

바로 카운트가 증가 할 수 있을 때는 언제일까? 생각해보면 '다음의 차'가 들어오는 시점이 '이전의 차'가 나가는 시점보다 느리면 ( 즉, 수가 크다면 ) 다음에 들어오는 차는 이전의 차들을 찍을 수 있는 카메라의 시선에서 벗어나기 때문에 설치의 개수를 즉각적으로 올려 주면 된다.

 

이후, 위의 케이스와 마찬가지로 새로운 설치 기준을 잡아준다.

 

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

  for (let i = 1; i < routes.length; i += 1) {
    const [start, end] = routes[i];
    // 끝나는 지점이 새로운 차가 들어오는 진입점보다 값이 크다는 것은
    // 새로운 차가 올라와도, 이전의 차가 도로 위에 존재 한다는 것인데
    if (start <= installation) {
      // 이 때, 이전의 차가 나가는 시점이 이후에 들어온 차보다 늦는다면
      // 이후의 차가 나가기 전에만 촬영이 되면 된다는 것이다. => 즉 이후에 들어온 차가 나가는 시점이 기준이 되고,
      if (end < installation) {
        installation = end;
      }
      // 그렇지 않다면 기준을 이전 차가 나가는 시간을 기준으로 유지한다.
    }
    // 만약에 올라 오는 시점보다 이전의 차가 먼저 나가면, 이전 차의 촬영을 위해 설치
    else {
      answer += 1;
      installation = end;
    }
  }

  return answer;
}