[프로그래머스] 단속카메라 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

2. 풀이과정

해당 문제는 카메라를 설치할 구간을 지정해 가며 최소한으로 카메라를 설치하는 개수를 구하는 문제이다.

차량의 이동 경로에서 진입 구간이 늦은 차량부터 살펴보며 카메라를 설치할 구간을 정한다.

다음 차량의 진입 구간이 이전 차량의 진출 구간보다 전에 있다면 두 차량의 이동 경로가 겹치게 되고 겹치는 지점에 카메라를 설치하면 카메라를 최소한으로 설치할 수 있다.

 

1. 차량의 이동 경로를 오름차순으로 정렬한다. routes.sort()
2. 처음 카메라를 설치할 구간을 제일 뒷 경로의 구간으로 정한다. camera = routes[0]
3. 다음 차량의 경로부터 하나씩 불러와 for i in routes[1 : ]
4. 만약 다음 차량의 고속도로 진입 지점이 이전 카메라 구간 안에 있으면 if (i[0] <= camera[1])
5. 카메라 설치 구간의 범위 겹치는 최대 범위로 줄여준다. camera = [i[0], min(camera[1], i[1])]
6. 반면에 다음 차량의 고속도로 진입 지점이 이전 카메라 구간을 넘어갔다면 else
7. 카메라를 설치할 구간을 새롭게 지정해 주고 camera = i
8. 카메라는 이전 구간에서 무조건 하나를 설치해야 한다. answer += 1
9. 마지막 구간에는 카메라를 설치하지 않고 종료되기 때문에 카메라를 하나 더 설치해 준다. answer += 1

반응형

3. 소스코드

def solution(routes):
    answer = 0
    
    routes.sort()
    camera = routes[0]
    for i in routes[1 : ]:
        if (i[0] <= camera[1]):
            camera = [i[0], min(camera[1], i[1])]
        else:
            camera = i
            answer += 1
    
    answer += 1
    return answer