[코딩테스트] 탐욕법(Greedy) - 단속카메라

---

문제

https://school.programmers.co.kr/learn/courses/30/lessons/42884

프로그래머스

 

은근 자주 나오는 문제 유형

 

1차원의 선 위에 두 점이 주어진 선분이 여러 개 중복되어 있을 때 몇 개의 점을 찍어야 모든 선분을 선택할 수 있는가

 

 

---

전략

 

01. 각 선분의 끝점을 기준으로 정렬하기

 각 선분의 끝점을 기준으로 정렬하고 첫번째 선분의 끝점을 선택하고 나면  그 사이에 몇 개의 선분이 있던지 전부 선택된다. 그렇게 선분을 읽어 나가다가 기존의 점이 포함되지 않는 선분이 있을 경우 그 선분의 끝점을 다시 새로운 카메라 지점으로 정하고 수를 센다.

 

카메라 위치 고르기

 

 

---

풀이

 

def solution(routes):
    routes.sort(key=lambda x: x[1])
    
    count = 0
    
    last_point = None
    
    for i in routes:
        if last_point in range(i[0], i[1] + 1):
            pass
        else:
            last_point = i[1]
            count += 1
    return count

 

 각 차량의 경로인 routes를 리스트의 sort()메소드를 이용해 끝점을 기준으로 정렬했다. 그리고 가장 최근 카메라를 놓는 지점을 last_point로 놓고 각 route를 읽어가면서 last_point가 기존 선분의 범위에 포함되어 있을 경우에는 pass하고 선분의 범위를 벗어나는 경우 그 선분의 끝점을 다시 새로운 last_point로 정하면서 count를 하나씩 세서 풀었다.

 

 

---

다른 사람의 풀이

 

def solution(routes):
    routes = sorted(routes, key=lambda x: x[1])
    last_camera = -30000

    answer = 0

    for route in routes:
        if last_camera < route[0]:
            answer += 1
            last_camera = route[1]

    return answer

 

 내 조건문은 각 route 범위 안에 들어 있는지 아닌지를 판단하느라 시간복잡도가 꽤 소요됐다. 만약 routes안의 요소들이 N개가 있고 각 route의 범위가 (-N, 0), (1-N, 1), ... 이런 식이었다면 O(N^2)의 시간복잡도가 소요되어 효율적이지 못한 알고리즘이 됐을 것이다.

 

 이 풀이는 각 last_camera가 각 route의 첫점을 지나는지 안 지나는지만 판단해서 답을 구했다. 보다시피 더 효율적인 알고리즘이다.