공부 기록장
[프로그래머스 - Python] 단속카메라 본문
https://school.programmers.co.kr/learn/courses/30/lessons/42884
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 요약
고속도로 이동하는 모든 차량이 단속용 카메라 한 번은 만나도록 카메라 설치
차량 경로가 주어질 때, 최소 몇 대의 카메라를 설치?
코드 설명
def solution(routes):
answer = 1
routes.sort(key =lambda x : x[1]) # 자동 a 기준으로 정렬
cam = routes[0][1]
for i in range(1,len(routes)):
if routes[i][0] <= cam:
continue
else:
cam = routes[i][1]
answer += 1
return answer
전형적인 그리디 문제이다.
차량들의 경로에서 최대한 겹치는 구간을 파악해, 최소한의 카메라를 설치하기 위해서는
routes를 진출 시점을 기준으로 정렬해야 한다.
routes를 진입 시점 기준으로 정렬하게 되면
routes[i][0] <= cam 인데, routes[i][1] <= cam인 경우에 대해서
routes[i] 루트 차량이 카메라를 한 번도 안 만나는 경우가 생길 수 있다.
다시 말해, 진출 시점에 대해서 오름차순으로 정렬해야
진출 지점에 카메라가 있다고 가정했을 때, 그 이후의 경로들의 진입 지점이 진출 시점보다 앞서면
반드시 그 카메라에 단속된다고 장담할 수 있다.
만약 진입 시점을 기준으로 정렬하고 싶다면
아래와 같은 풀이가 가능하다.
# 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지
def solution(routes):
routes.sort() # 들어온 지점에 따라 오름차순 정렬
answer = 1 # 카메라 개수
start, end = routes[0][0], routes[0][1]
for i in routes[1:]:
if start <= i[0] <= end:
start = i[0] # 범위안에 있으면 시작점을 바꿔줌
end = min(end, i[1])
else:
start, end = i[0], i[1]
answer += 1 # 범위 안에 없기때문에 카메라 추가
return answer
배운 점
- 주어지는 입력 예시 이외의 가능한 상황도 생각해야 한다
참고 자료