[CodeKata] 프로그래머스: 11.28(일), 단속 카메라

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

내 풀이는, check라는 배열을 만들어서 차들이 지나가는 구간에 해당하는 인덱스값들을 1씩 더해준다. (4대가 지나가는 경우, 4가 됨)

이걸 다시 역으로, 가장 많은 차가 지나가는 인덱스를 찾고, 여기에 해당하는 구간들을 다시 check에서 1씩 빼준다.

 

우선, 우려했던 효율성 테스트에서 실패가 떴을뿐더러, 테스트 케이스 외 실제 정확성 테스트도 다 실패가 떴다.

좀 더 효율적인 비교방법을 모범답안을 통해 학습해보고자 한다.

function solution(routes) {
  var answer = 0;
  routes = routes.map(([a,b]) => [Math.min(a,b), Math.max(a,b)])
  let [min,max] = routes.flat().sort((a,b) => a-b).slice().filter((_,i) => i === 0 || i === routes.length*2-1);
  if (min < 0) {
    const comp = -min;
    min += comp
    max += comp
    routes = routes.map(([s,e]) => [s+comp, e+comp])
  }
  
  let check = new Array(max-min+1).fill(0);
  for (let [s,e] of routes) {
    for (let i = s ; i <= e ; i++) check[i]++;
  }
  
  let cars = routes.length;
  while (cars > 0) {
    let idx = check.indexOf(cars);
    while (idx !== -1) {
      if (routes.find(([s,e]) => s <= idx && e >= idx)) {
        routes.filter(([s,e]) => s <= idx && e >= idx).forEach(([s,e]) => {
          for (let i = s ; i <= e ; i++) check[i] -= 1;
        })
        answer++
      }
      idx = check.findIndex((e,i) => e === cars && i > idx);
    }
    cars--;
  }
  
  return answer;
}

 

🖇 리뷰

const solution = (routes) => {
  let answer = 0;
  routes.sort((a, b) => {
    return a[1] - b[1];
  });
  let camera = -30001;
  for (let i = 0; i < routes.length; i++) {
    if (camera < routes[i][0]) {
      answer++;
      camera = routes[i][1];
    }
  }
  return answer;
};

* 출처 :  https://kyun2da.github.io/2020/07/20/checkCamera/ 

 

• routes를 진출시점(1번째 요소) 기준 오름차순으로 정렬한다.
• camera를 최소값인 -30000 보다 작은 -30001로 초기설정 한다. 이를, 갱신하면서 routes 각 요소들을 검사가능한지 판정한다.
• routes를 순회하며, 현재 요소의 진입시점(0번째 요소)이 camera보다 작다면 현재 카메라로 검사가 불가한 것이다. 이 때, 카메라 1대를 추가설치한다는 의미리 answer을 1을 더하고, camera를 현재 요소의 진출시점(1번째 요소) 로 갱신한다.
• 마지막으로, 모든 카메라 대수인 answer를 반환한다.

 

생각보다 매우 간단하게 풀 수 있는 문제였...다.(😂😂) Greedy 알고리즘의 핵심인 어떻게 조건을 갱신할지를 좀 더 고민해보도록 해야겠다.