23.03.03 파이썬 코딩 퀴즈#182 단속카메라(프로그래머스 스쿨)

이번 문제는 단속카메라 문제이다.

고속도로를 이동하는 모든 차량을 단속하기 위해 필요한 최소 카메라 개수를 구해야 하는 문제이다.

전달되는 routes 는 각 차량(index)별로 진입,진출 시점이 좌표 형태로 전달된다.

해당 문제 역시 수학적 사고가 요구된다.

진입/진출 지점을 각기 다른 지점으로 생각하면 안된다. 그냥 하나의 도로에서 어떤 지점에서 들어와서 쭉 진행하다가 특점 지점에서 해당 도로를 탈출했다고 봐야 한다.

입출력 예제를 보면 저렇게 선을 그은 지점에 카메라를 설치하면 모든 차량이 카메라를 만나게 된다.

쉽게 생각하면, 차량의 진입 시점이 이전 차량의 진입/진출 시점 사이에 있거나 같은 경우라면 한대의 카메라로 두대의 차량을 단속 할 수 있다.

 

하지만 이 경우라면 어떨까?

분명 모든 차량들이 0번 차량의 진입/진출 시점 안에 위치하지만, 각기 다른 지점에 카메라의 설치가 필요하다.

즉, 이 경우에는 0번 차량이 아닌 1번 차량을 기준으로 카메라가 설치가 된다.

다시 말하자면, 진입 시점이 아닌, 진출시점을 기준으로 정렬이 필요하며, 진출 시점이 가장 빠른 차량을 진출 지점에 카메라를 설치하면서 다른 차량의 진출 시점과 맞추어 보면 된다.

최대한 직관적으로 보기 위해서 이중 반복문을 선택하였다.

정렬된 배열 routes에서 원소를 하나씩 뽑아 자기 자신과 비교하면서 반복문을 시행한다.

이 때, start(기준차량)의 진출 시점이 다른 차량의 진입 진출 사이에 위치한다면 section 값을 증가시키고 해당 차량의 index를 installed 에 저장한다.

그리고 section 값이 존재할때 answer 의 값을 1 증가 시킨다.

첫번째 작성한 코드를 좀 더 줄여서 작성한 두번째 코드이다.

차량의 진출시간 기준으로 오름차순 정렬은 동일하다. 다만 camera라는 변수에 가장 진출시간이 빠른 차량의 진입시간 직전의 시간대로 카메라를 설치한다. (배열에 영향을 미치지 않는 가장 앞 부분)

이제 반복문을 통해서 각 차량을 비교하게 되는데, 새로운 카메라가 설치되는 시점은 바로 차량의 진입 시간이 현재 카메라 위치보다 늦은 경우이다. (값이 큰 경우이며, 작거나 같은 경우라면 해당 카메라를 만난다는 뜻이다.)

그리고 카메라 설치가 필요한 경우라면 차량은 진출 시점에 맞춰서 설치해주면 된다.

레벨이 높아질 수록, 점점 수학적 논리적 사고를 요하는 문제들이 많아졌다.