[프로그래머스] Swift - 단속카메라 (LV.3)

👆문제풀러 가기👆

문제 설명

 

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

 

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

---

이 문제는 Swift로 풀지 못하게 되어 있다. 근데 그냥 풀었다.. 아이디어로 구현만 하면 되니까...

문제가 굉장히 심플하다. 풀이도 심플하다.

하지만 풀이를 떠올리지 못한다면 지옥같을 지도 모르겠다. 그것이 그리디니까..

 

풀이

// MARK: - 단속카메라 LV.3. Swift는 억울해
func solution(_ routes: [[Int]]) -> Int {
    var routes = routes.sorted(by: {$0[1] < $1[1]}) // 진출시점을 기준으로 오름차순
    var result = [routes.removeFirst()[1]]          // 첫번째 카메라 위치 저장.

    for route in routes {
        guard let cameraPosition = result.last else { continue } // 현재 카메라 위치(가장 뒤에 위치한 카메라 위치)
        let entryPoint = route[0] // 진입 시점
        let exitPoint = route[1]  // 진출 시점

        if entryPoint > cameraPosition { // 진입구간이 현재 카메라 설치 위치보다 뒤쪽에 위치하면, 카메라 설치.
            result.append(exitPoint)
        }
    }

    return result.count
}

 

 

이 문제는 코드가 몹시 간단해서, 주석과 함께 본다면 충분히 설명이 될 것이라 생각한다.

그래도 설명을 하자면,

1. 모든 차량은 CCTV(카메라)에 찍혀야 한다.
   • 각 차량의 구간 중, 한 지점에서만 보이면 된다.
   • 따라서, 진입, 진출 시점 둘 중 하나를 기점으로 잡으면 좋을 것이다.
   • 하지만 진입 시점으로 하게 되면 A가 [1, 5] B가 [2, 3]일 때, A는 이미 카메라에 확인이 되는데, B를 위해 한 대의 카메라를 더 설치해야하는 낭비가 발생한다. 그러니 진출 시점으로 정렬을 하자.
2. 진출 시점으로 정렬을 하게 되면, 끝이다. 
   • B가 [2, 3], A가 [1, 5]에서 [진입, 진출]한다고 가정할 때, 3지점에 하나를 설치하면 충분하다.
   • 즉, 앞 차량의 진출 시점(3)보다, 뒷 차량의 진입 순서(1)가 먼저일 때는 CCTV를 설치하지 않아도 된다.
   • 진입 시점이 앞 차량의 진출 시점보다 늦을 때만 카메라를 추가하자.