[프로그래머스 level3 단속카메라] 그리디 활용하기

해결해야하는 문제는 다음과 같았다.

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

코딩테스트 연습 - 단속카메라

 

정확성만을 고려한 아이디어는 다음과 같다.

 

 

아이디어를 바탕으로 작성한 코드는 다음과 같다.

def solution(routes):
    answer = 0
    INF = int(1e9)
    while routes :
        min_routes = INF
        max_routes = -30001
        car_arr = [0]*(60002)
        for s,d in routes:
            car_arr[s+30000] += 1
            car_arr[d+30000] += -1
            if d > max_routes :
                max_routes = d
            if s < min_routes :
                min_routes = s

        min_routes += 30000
        max_routes += 30000
        for i in range(min_routes,max_routes+1):
            car_arr[i] += car_arr[i-1]

        find_index = car_arr.index(max(car_arr))
        i=0
        while i < len(routes):
            if routes[i][0]+30000 <= find_index and routes[i][1]+30000 >= find_index :
                routes.pop(i)
            else :
                i+=1
        answer += 1

    return answer

 

 

하지만 이는 효율성을 통과하지 못한다.

따라서, 효율성을 위해 다음과 같은 생각을 하였다.

 

 

 

이러한 아이디어를 바탕으로 작성한 코드는 다음과 같다.

def solution(routes):
    answer = 0
    while routes :
        routes.sort(reverse=True,key=lambda x : x[1])
        s,d=routes.pop()
        i=0
        while i < len(routes):
            if routes[i][0]<= d and routes[i][1] >= d:
                routes.pop(i)
            else :
                i+=1
        answer += 1

    return answer

 

 

이런 문제는 광고삽입 문제와, 추석 트래픽 문제와 시간/거리를 다룬다는 점에 있어서 비슷하다고 생각하였다...

(

광고 삽입 : https://kom-story.tistory.com/345

추석 트래픽 : https://kom-story.tistory.com/84

)

효율성면에서 한번에 통과하지 못하는것이 반복되는데, 더 좋은 알고리즘이 무엇인지에 대해 생각하는 힘을 길러야할 것 같다!!