[문제 바로가기] https://programmers.co.kr/learn/courses/30/lessons/42884
📌문제 설명
고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.
제한사항
- 차량의 대수는 1대 이상 10,000대 이하입니다.
- routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
- 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
- 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.
입출력 예
입출력 예 설명
-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.
-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.
💡 문제 풀이
탐욕법(Greedy)으로 해결한 문제!
처음에는 차량의 이동 경로를 하나의 배열로 다 표시하여 가장 많이 겹치는 부분부터 제거할까 했지만 제한사항에서
- 차량의 대수가 10,000대
- 진입, 진출 지점이 -30,000이상 30,000이하
라고 했기 때문에 시간, 공간 복잡도 둘 다 비효율적일 거라 생각했다.
따라서, 전체가 아니라 routes 배열에 있는 원소를 하나씩 탐색하면서 최소 몇 대의 카메라를 설치해야 하는지 계산하였다.
step 1)
카메라 설치 개수를 파악하기 위해서 먼저 고속도로에 진입한 지점을 기준으로 routes를 정렬하였다.
step 2)
첫 번째 지점을 출발점으로 선정하고
- start : 현재 고속도로 집입 지점
- end : 현재 고속도로 진출 지점
이후에 나오는 원소들(route)에 대해서 3가지 경우로 나누어 처리하였다.
최소의 카메라를 설치하기 위해서는 가장 많이 겹치는 구간에 설치해야 되기 때문에 겹치는 부분이 존재할 경우 해당 구간을 start, end로 최신화해주고 그렇지 않으면 비교하는 route의 진입/진출 구간을 start, end로 최신화해준다.
이 때, 겹치는 부분이 존재하면 당연히 추가의 카메라를 설치할 필요가 없지만 겹치는 부분이 존재하지 않는 3번째 경우에는 answer + 1을 해주어 카메라 설치 개수를 추가한다.
step 3)
routes 배열의 탐색을 모두 마치면 answer 변수에 저장한 카메라 설치 개수 값을 return한다.
코드는 다음과 같다.
def solution(routes):
answer = 1
routes = sorted(routes, key=lambda x:[x[0], -x[1]])
start, end = routes[0][0], routes[0][1]
for idx in range(1, len(routes)):
if routes[idx][1] <= end:
start, end = routes[idx][0], routes[idx][1]
elif routes[idx][0] <= end and routes[idx][1] > end:
start = routes[idx][0]
else:
answer += 1
start, end = routes[idx][0], routes[idx][1]
return answer다른 사람의 풀이
def solution(routes):
routes = sorted(routes, key=lambda x: x[1])
last_camera = -30000
answer = 0
for route in routes:
if last_camera < route[0]:
answer += 1
last_camera = route[1]
return answer고속도로의 처음 지점이 아닌 끝 지점부터 시작하여 개수를 파악하였다.
또한, 나의 풀이는 3가지 경우로 나누어서 다음 route와 비교하였는데
위 풀이는 간단하게 겹치는 구간의 유무로만 나누어서 카메라 개수를 추가하였다.
