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

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

프로그래머스

Status : Solved

Time : ??????

 

---

 

문제 설명

 

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

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

 

입력 및 출력

 

제한사항

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

 

입출력 예

routes	return
[[-20, -15], [-14, -5], [-18, -13], [-5, -3]]	2

 

 

---

 

풀이

레벨 3을 부여받았지만, 구현의 난이도보다는 문제 설정 및 해결로써의 난이도에 가깝다. 풀고 나서 "왜 이게 레벨 3이지?"라는 질문글을 많이 봤었는데, 사실 나는 코딩의 본질이 "주어진 상황과 자원 하에서 가장 효율적으로 동작하는 프로그램을 만드는 것"이라고 생각해서 충분히 레벨 3 정도의 난이도를 부여받을 수 있었다고 본다. 처음에는 가장 많이 겹치는 지점부터 일일히 제거해보려다가 좀 시간을 낭비하기도 했었고....

 

핵심은 어디에 단속카메라를 둘 것인가? 에서부터 출발한다. 모든 차량은 최소 1개 이상의 단속카메라를 만나야 하므로, 우리는 쉽게 차량 이동 경로가 많이 교차하는 지점을 우선으로 두어야 한다고 생각할 수 있다. 차량 한 대(혹은 두 대)를 기준으로 본다면 다음 세 경우가 발생한다.

• 교차점이 아예 없는 경우 : 이 경우는 어디에나 단속카메라를 두어도 된다
• 다른 차량 이동 경로에 포함되거나, 포함하는 경우 : 이동 경로가 더 짧은 쪽에 단속카메라를 두어도 된다.
• 위 경우에 포함되지 않으며, 다른 차량 이동 경로와 겹치는 경우 : 이 경우는 한 차량의 출발지와 다른 차량의 도착지가 서로 다른 각각의 이동 경로에 포함된다. 즉 겹치는 부분의 출발지 - 도착지에 단속 카메라를 두어야 한다.

이 세 가지 경우를 모두 만족시키는 위치로 우리는 도착지를 기준으로 삼을 수 있다. 즉 우리는 그리디하게 다음 알고리즘을 사용해 볼 수 있다.

1. route 리스트를 도착지를 기준으로 정렬한다.
2. route 안의 차량을 처음부터 끝까지 순회한다. 초기 기준 도착지는 첫 번째 차량의 도착지가 된다.
3. 2에서 만약 출발지가 기준 도착지보다 앞선다면, 도착지의 감시카메라로 커버 가능한 이동경로이므로 계속 진행한다.
4. 2에서 만약 출발지가 기준 도착지보다 뒤에 있다면, 이 도착지의 감시카메라로 커버 불가능한 이동 경로이다. 따라서 answer를 1 증가시키고 기준 도착지를 현재 이동 경로의 도착지로 설정한다.

말로 하면 복잡해 보이지만, 코드는 매우 짧아짐을 알 수 있다!

 

풀이 코드

def solution(routes):
    routes.sort(key = lambda x : x[1])
    answer = 1
    prev_end = routes[0][1]
    for start, end in routes :
        if start > prev_end :
            answer += 1
            prev_end = end

    return answer