프로그래머스 Lv3. 단속카메라 (파이썬)

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

프로그래머스

 

<문제 설명>

• 각 차량이 단속용 카메라를 최소 한번은 만나야 한다.
• routes 배열에는 각 차량의 출발지점 & 도착지점이 들어있다.
• 출발지 또는 도착지에 카메라가 있어도 카메라를 만난것으로 간주한다.

-> 모든 차량이 단속용 카메라를 만나기 위한 카메라의 최소 개수는?

 

<문제 접근>

배열의 겹치는 부분을 찾되 최소한의 카메라를 놓아야 한다.

테스트 케이스를 보면 겹치는 부분은 세군데이지만 카메라는 두개만 있어도 모든 차량이 카메라를 만나게 된다.

이런 경우는 도착지를 기준으로 2차원 배열을 정렬한 후 출발지를 비교하는 방식을 사용하면 풀 수 있다.

 

<문제 해결>

1. 도착지를 기준으로 정렬한다.

2. 배열의 가장 앞에 있는 차량의 인덱스를 s_i로 놓는다. 

3. 반복문을 돌면서 i번째 차량의 출발지가 s_i번째 차량의 도착지보다 클경우(두 차량의 경로가 겹치지 않음을 의미한다)

    카메라 수를 한개 증가시키고 s_i = i로 변경한다. 

if 문 안에 s_i=i를 넣지 않은 이유는 for문을 모두 돌았을 때도 s_i=i로 변경해야 while문이 종료되기 때문에 바깥으로 뺐다.

 

def solution(routes):
    answer = 1
    routes.sort(key=lambda x:x[1])
    s_i=0 
    while s_i<len(routes)-1:
        for i in range(s_i+1,len(routes)):
            if routes[s_i][1]<routes[i][0]:
                answer+=1
                break
        s_i=i
    return answer