[Python] Lv3. 단속카메라

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

문제 아이디어)

모든 차량이 적어도 한 번은 카메라를 지나야 한다.

매 순간, 차량의 진출 지점에 카메라를 설치하는게 최선의 선택이다

왜 진입 지점이 아닌 진출 지점으로 정렬하는가?

=> 진출지점으로 정렬해야 최소 카메라 설치 가능함 

 

 

**카메라 설치**

첫 번째 차의 진출 지점에 카메라 설치하고, 그 카메라가 다음 차량도 커버할 수 있는지 확인한다

이후 카메라가 다음 차량의 진입 지점보다 앞에 있으면 그 카메라가 그 차량도 커버할 수 있기 때문에

추가적인 카메라 설치는 필요없다.

카메라가 다음 차량의 진입 지점을 커버하지 못한다면, 해당 차량의 진출 지점에 새로운 카메라 설

 

 

시간복잡도

경로 배열을 정렬해야한다 -> O(n log n)

차량의 경로는 하나씩 탐색한다 -> O(n)

O(n log n)이고 n은 최대 10000이므로 시간안에 가능 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

 

1. 진출 지점 기준 오름차순 정렬

2. 경로 routes들을 하나씩 살펴보면서

     1) 현재 카메라의 위치가 차량의 진입 지점을 커버할 수 없는 경우

     2) 카메라를 해당 차량의 진출 지점에 설치

     3) 카메라 설치 후 횟수 증가 

 

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

첫번째 시도

-> 단순히 종료 지점끼리만 비교함, 카메라 어디에 설치할지 결정하는 로직이 부재 

def solution(routes):
    answer = 0
    for i in range(len(routes)): 
        for j in range(i+1, len(routes)):
            if routes[i][1] >= routes[j][1]:
                answer+=1      
    return answer

 

 

정답코드

def solution(routes):
    answer = 0
    camera = -30001
    routes.sort(key=lambda x: x[1])
    for route in routes:
        if camera < route[0]:
            camera = route[1]
            answer+=1

    return answer

 

어떤 기준으로 정렬하는지 중요한것 같다.