[프로그래머스] 단속 카메라 - python파이썬

문제

 

 

일단 이 문제를 보고 먼저 진입지점이 제일 작은순 그리고 그다음으로는 진출 지점이 작은 순으로 정렬을 해준 후에 겹치는 범위에 대해 필요한 카메라 개수를 계산하면 되겠다고 생각했다.

 

정렬

routes.sort(key = lambda x:[x[0],x[1]])

 

 

먼저 이렇게 정렬을 수행 해준 후에 start, end 로 진입, 진출 범위의 값을 저장해 해당 범위를 벗어나는 경로를 만나면 start, end를 업데이트 해주어 다음에 카메라를 둘 지점에 대해서 구하도록 해주었다.

 

 

나의 코드

def solution(routes):
    answer = 1
    routes.sort(key = lambda x:[x[0],x[1]])
    start = routes[0][0]
    end = routes[0][1]
    
    for i in range(1,len(routes)):
        #이전 범위와 겹칠때
        if start<= routes[i][0] <= end:
            start = routes[i][0]
            #이후에 온 경로의 끝나는 지점이 기존의 범위의 끝나는 지점보다 작을시 end값 업데이트
            if routes[i][1]< end:
                end = routes[i][1]
            continue
        #새로운 범위가 필요할 때
        else:
            answer+=1
            start = routes[i][0]
            end = routes[i][1]
        
    return answer

 

 

처음에 문제를 풀 때는 이전범위와 겹칠때 start만 업데이트 해주어서 오답이 나왔었다

 

하지만 이후에 온 경로의 끝나는 지점이 기존의 end 보다 더 작은 경우가 있기 때문에 이러한 경우에는 end 를 업데이트 해주어야한다.

 

이 문제풀이를 요약하자면 범위가 겹칠때마다 겹치는 범위로 범위를 업데이트 해주면서 해당 범위를 벗어나는 경로를 마주할 때까지 겹치는 범위를 업데이트 해주는 것이다.

그리고 범위를 벗어나는 경로를 마주하면 start,end를 새로운 경로의 범위에 맞게 갱신해주고 다시 겹치는 범위에 있는 경로를 찾아주면 된다.

 

이때 마지막 범위에 대해서는 카운트가 되지 않기 때문에 answer 는 1로 초기화 해주어야한다.

그리고 기존의 범위를 벗어난 경로를 마주한다면 기존의 범위에 필요한 카메라를 answer에 +1 해주어야되기 때문에 범위가 바뀔때마다 answer += 1을 해주었다.

 

 

Level3인 것 치고는 간단하게 풀렸던 것 같다.