[Sorting & Greedy] 단속카메라 (프로그래머스 강의)

문제

https://school.programmers.co.kr/learn/courses/14760/lessons/125471

• 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

• 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

입출력 예시

풀이

그리디 알고리즘이란

선택의 순간마다 당장 눈 앞에 보이는 최고의 상황을 쫓아 최종적인 해답에 도달하는 방법이다.
실제 코딩테스트에서는 그리디 알고리즘을 선택하고 사용할 때, 반례가 없는지 확인하는 방식으로 그리디 알고리즘을 활용하기 적절한 문제인가를 결정할 수 있다.

💡 아이디어

• 겹치는 지점에 최대한 카메라를 많이 설치해야 최소 개수의 카메라를 설치할 수 있다.
• routes 배열의 [진입시점, 진출시점] 값 중 진출시점을 기준으로 배열을 정렬한 뒤, 각 배열의 값을 하나씩 확인하면서 문제를 해결할 수 있다.

  🚘 앞 차량의 진출시점과 뒷 차량의 진입 시점을 비교하여
  1) 앞 차량의 진출시점 > 뒷 차량의 진입시점 이면 앞 차량의 진출시점에 카메라를 설치한다. 그 뒷 차량의 진출시점들을 모두 비교하면서 진입시점이 앞 차량의 진출시점보다 커지는 경우까지 탐색한다.
  2) 앞 차량의 진출시점 < 뒷 차량의 진입시점 이 되면 카메라를 한 대 추가하여 설치하고, 그 뒷 차량들에 대해 1) 과정을 계속 반복한다.

코드

def solution(routes):       # routes: 차량의 진입진출 정보
    answer = 0
    routes.sort(key = lambda x : x[1])      # 차량 정보를 진출 시점을 기준으로 정렬함
    
    point = routes[0][1]      # 첫 번째 차량의 진출지점을 포인트 지점으로 초기화
    answer = 1                # 카메라 한 대를 첫 번째 차량의 진출지점에 설치했으므로, 카메라 개수를 1개 추가함
    for i in range(1, len(routes)):
        if point < routes[i][0]:        # 현재 포인트 지점보다 새로운 차량의 진입지점이 더 크면 (겹치는 영역이 없으면) 포인트 지점을 바꿔주고, 카메라 한 대를 세움
            answer += 1                 # 카메라 개수 count
            point = routes[i][1]        # 포인트 지점 갱신
            
    return answer

실행 결과 출력