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

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

 

 

---

 

첫번째 풀이

// 한번은 만나게 최소 몆대 설치해야함?
function solution(routes) {
    // 빨리 나간 순으로 정렬
    routes.sort((a, b) => a[1] - b[1]);
    const camera = [routes[0][1]]; // 첫번째 카메라
    
    for (let i = 1; i < routes.length; i++) {
        const [start, end] = routes[i];
        // 이전의 카메라를 만난적 없음 카메라 추가
        if (!isMet(start, end, camera)) {
            camera.push(end);
        }
    }
    return camera.length;
}

function isMet(currStart, currEnd, prevCam) {
    for (const time of prevCam) {
        if (currStart <= time && time <= currEnd) {
            return true;
        }
    }
    return false;
}

 

 

 

두번째 풀이 (그리디)

 

이전 차가 나간 시각 < 현재 차가 진입한 시각 일 때 카메라를 현재차가 나간시각에 추가한다.

 

function solution(routes) {
    var answer = 0;
    let lastCamera = -Infinity;
    // 빨리 나가는 순으로 정렬
    routes.sort((a, b) => a[1]-b[1]);
    
    for (const [start, end] of routes) {
        if (lastCamera < start) {
            answer++;
            lastCamera = end;
        }
    }
    return answer;
}