프로그래머스: 단속카메라

route들이 최대한 잘 겹치게 만드는 것이 목표인 문제이다.

이런 문제는 input의 순서를 강제하는 것이 큰 도움이 되는 경우가 많은데,

여기서는 routes를 사전에 정렬하는 것이 이에 해당된다.

정렬이 필요한 이유에 대해서는 생각해 볼 필요가 있는데,

이 문제에서는 group간 겹치는 문제를 회피하기 위해서이다.

 

아래 예제를 보자.

[[-20,-15], [-14,-5], [-18,-13], [-5,-3]]

groups = [[-20, -15]

정렬하면, [[-20, -15], [-18, -13], [-14, -5], [-5, -3]]

1) [-18, -13] 처리

group 내의 [-20, -15]와 겹치므로 group[0]를 [-20, -15]와 [-18, -13]의 교집합인 [-18, -15]로 처리한다.

따라서 group = [[-18, -15]]

2) [-14, -5]

group 내에 겹치는 원소가 없다.

따라서 group = [[-18, -15], [-14, -5]]

3) [-5, -3]

group 내에 [-14, -5]와 겹친다.

따라서 group = [[-18, -15], [-5, -5]]

def solution(routes):
    routes.sort()
    groups = [routes[0]]
    for i in range(1, len(routes)):
        route = routes[i]
        grouped_Flag = False
        for j, group in enumerate(groups):
            if route[0] <= group[1]:
                groups[j] = [route[0], min(route[1], group[1])]
                grouped_Flag = True
                break
        if not grouped_Flag:
            groups.append(route)
    return len(groups)