프로그래밍/코딩테스트 문제풀이

[Python] 프로그래머스. 단속카메라 (Level 3)

inspirit941 2019. 11. 27. 18:34
반응형

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

 

코딩테스트 연습 - 단속카메라 | 프로그래머스

[[-20,15], [-14,-5], [-18,-13], [-5,-3]] 2

programmers.co.kr

차량의 진입 / 진출지점이 겹치면, 겹치는 지점의 공통범위로 감시카메라의 범위를 좁힌다.

감시카메라 범위에 포함되지 않을 경우 새 카메라를 설치해야 한다.

 

코딩테스트 초창기에 접했던 문제라서 푸는 데 정말 오래 걸렸었다.

 

 

def solution(routes):
# 도로의 맨 앞에서부터 감시카메라 설치.
routes = [[i[0], i[1]] for i in sorted(routes, key = lambda x: (x[0]))]
result = [routes.pop(0)]
for compare in routes:
idx = 0
while idx != len(result):
# 만약 새 차량의 진입시점 / 진출시점이 기존 카메라 설치 범위에 들어간다면
if (result[idx][0] <= compare[0] <= result[idx][1]) or (result[idx][0] <= compare[1] <= result[idx][1]):
# 감시카메라가 새 차량을 감지할 수 있도록 감시카메라의 위치 조정
result[idx][0] = compare[0] if compare[0] > result[idx][0] else result[idx][0]
result[idx][1] = compare[1] if compare[1] < result[idx][1] else result[idx][1]
break
else:
idx +=1
# 만약 감시카메라 설치 위치를 전부 돌았는데도 감지가 안 된다면
# 차량을 감시할 수 있는 새 감시카메라를 설치해야 한다.
if idx == len(result):
result.append(compare)
return len(result)
반응형