[프로그래머스][Python] 단속카메라, level 3
문제
문제 설명
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 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 |
입출력 예 설명
-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.
접근
활동 선택 문제
겹치는 지점의 최소 갯수를 구하는 것이
결국 전체 경로 중 겹치치 않는 경로들의 최대 갯수를 구하는 것임을 알게 되는데
좀 오래 걸렸다.
왜 그럴까
우선 입출력 예시로 나와있는 경로를 그려보면 다음과 같다
왼쪽에서 부터 오른쪽으로 각각 1번부터 4번 경로라고 이름 붙일 때,
1번 경로는 2번과 겹치고
2번 경로는 3번과,
3번 경로는 4번과 겹친다.
이렇게 볼 때 겹치는 구간은 총 3개이며
이중에 어떤 겹치는 구간을 선택해야 모든 경로를 커버할 수 있는 카메라 설치 댓수를 최소로 할 수 있을지 고민했다.
뿐만아니라 이렇게 접근 할 경우 다른 어떤 경로와도 겹치지 않는 경로에 대해서는 어떻게 판단해야하는지 감이 오지 않았다.
그렇구나
결국 겹치는 구간의 최소값을 구한다는 뜻은
겹치지 않는 경로들의 그룹을 최소로 나눈다는 의미와 같다.
그리고 이런 그룹들은 "겹치는 구간"으로 표현될 수 있다.
위 그림에서 1번과 2번이 겹치는 구간은 (-18 ~ -15) 이며
2번과 3번이 겹치는 구간은 (-14 ~ -13) 이다.
따라서 둘은 다른 그룹에 속하고
(1번, 2번)을 하나의 그룹이라고 할 때
3번은 이 그룹에 속하지 못하는 경로라고 할 수 있다.
이어서 3번과 4번을 보면
둘은 (-5 ~ -5)에서 겹치는 경로로
(3번, 4번)은 같은 그룹으로 묶을 수 있다.
그리고 여기서 그룹이라고 이야기한 개념은 결국
각 그룹 내에서 가장 처음 선택된 경로만을 선택하는것으로
활동 선택 문제와 동일한 방식으로 풀이 가능하다는것을 알 수 있다.
활동 선택 문제는 한정된 자원을 이용하기 위한 여러 중복된 활동 중 겹치지 않는 활동들을 최대로 선택하는 문제로,
주어진 문제에서 겹치는 구간을 최소로 선택하는것은
겹치는 활동을 제외하고 스케줄링하는 활동 선택 문제와 같은 결과를 만든다.
활동 선택 문제는 겹치지 않는 활동을 선택하기 위해 이전에 선택한 활동과 겹치는 활동들을 모두 버리고,
이 문제는 겹치는 경로들을 하나의 그룹으로 표현하기 위해 각 그룹내의 처음 하나의 경로를 제외하고는 모두 버린다.
코드
전체 코드는 아래와 같다.
def solution(routes: list):
answer = 1
routes.sort() # 1
e = routes[0][1]
for i in range(1, len(routes)):
cur = routes[i]
if e >= cur[0]: # 2
e = e if e < cur[1] else cur[1]
else: # 3
answer += 1
e = cur[1]
return answer주석 1번
전체를 한번만 순회하여 그룹을 판단하기 위해서는
시작점 기준 오름차순 정렬이 필요하다
주석 2번
현재 경로의 시작점(cur[0])이 현재 그룹의 끝점(e) 이하일 경우,
현재 경로는 현재 그룹에 속하는 경로이다.
이때 끝점을 갱신해주어야 하는데,
현재 경로로 그룹의 범위가 더 좁아질 수 있기 때문이다.
만약 현재 경로의 끝점(cur[1])이 그룹의 끝점(e)보다 작을경우,
그룹의 범위를 좁혀야 하므로,
그룹의 끝점(e)을 현재 경로의 끝점(cur[1])으로 갱신한다.
아닐경우는 그룹의 끝점(e)을 그대로 유지한다.
주석 3번
만약 현재 경로가 현재 그룹에 속하지 않는 경로일 경우.
새로운 그룹이 시작되므로,
그룹의 수를 1증가시키고
그룹의 끝점을 현재 경로의 끝점으로 갱신시켜준다.
