프로그래밍/코딩테스트 문제풀이
[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

차량의 진입 / 진출지점이 겹치면, 겹치는 지점의 공통범위로 감시카메라의 범위를 좁힌다.
감시카메라 범위에 포함되지 않을 경우 새 카메라를 설치해야 한다.
코딩테스트 초창기에 접했던 문제라서 푸는 데 정말 오래 걸렸었다.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
반응형