풀이 과정
- 진입 시점 기준으로 내림차순으로 정렬해주고, 첫번째 진입 시점에 카메라를 둔다.
- 반복문을 돌면서 현재 진입 시점 ~ 진출 시점
- 카메라가 있다면 pass
- 카메라가 없다면 현재 진입 시점에 카메라 한대 추가 설치
- 진입시점 기준으로 내림차순으로 정렬해 주었으므로, 이전 단계의 카메라 위치는 어차피 겹치거나 도달하지 않으므로 필요 없음.
- 카메라의 개수 리턴
소스 코드
def solution(routes):
answer = 1
routes.sort(reverse=True)
# "진입 시점 기준으로 내림차순 정렬"
camera = routes[0][0]
for i in range(1, len(routes)):
# 현재 진입 시점~진출 시점 사이에 카메라가 있다면 pass
# 카메라가 없다면 해당 진입 시점을 카메라의 위치로
if routes[i][0] <= camera and camera <= routes[i][1]:
pass
else:
answer += 1
camera = routes[i][0]
return answer
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges
'알고리즘[Python] > 프로그래머스' 카테고리의 다른 글
[ Lv 3 ] 거스름돈 (0) | 2021.07.22 |
---|---|
[ Lv 3 ] 매칭 점수 (0) | 2021.07.21 |
[ Lv 3 ] 가장 긴 팰린드롬 (0) | 2021.07.20 |
[ Lv 3 ] [ 1차 ] 셔틀버스 (0) | 2021.07.20 |
[ Lv 3 ] [ 1차 ] 추석 트래픽 (0) | 2021.07.19 |