풀이 과정

  1. 진입 시점 기준으로 내림차순으로 정렬해주고, 첫번째 진입 시점에 카메라를 둔다.
  2. 반복문을 돌면서 현재 진입 시점 ~ 진출 시점
    • 카메라가 있다면 pass
    • 카메라가 없다면 현재 진입 시점에 카메라 한대 추가 설치
  • 진입시점 기준으로 내림차순으로 정렬해 주었으므로, 이전 단계의 카메라 위치는 어차피 겹치거나 도달하지 않으므로 필요 없음.
  1. 카메라의 개수 리턴

소스 코드

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

+ Recent posts