[프로그래머스] 단속카메라

https://school.programmers.co.kr/learn/courses/30/lessons/42884?language=python3

많이 풀어봤던 유형인데 한 동안 안 접하다보니까 어떻게 접근해야할 지 모르겠는 문제다.

시도1 - 실패

def solution(routes):
    answer = 0
    
    routes.sort()
    
    road = [0] * 60001
    
    for r in routes:
        r[0] = r[0] + 30000
        r[1] = r[1] + 30000
        
        for i in range(r[0], r[1]+1):
            road[i] += 1
    
    road.sort(reverse=True)
    
    cars = len(routes)
    
    idx = 0
    
    while cars > 0:
        cars -= road[idx]
        idx += 1
        answer+=1
        
    return answer

좌표겸 배열을 만들어서 각 좌표가 몇 번 겹치는지 셌다. 그러고 많이 겹치는 순서대로 겹치는 횟수를 전체 차량 수에서 빼면서 답을 구했다. 그리고 틀렸다. 아예 전부 다 틀렸고 시간초과도 있었다. 아무래도 차량 여러대가 겹치는 구간이 많을 때 오류가 발생하는 것 같다.

시도 2 - 실패

def solution(routes):
    answer = 0
    
    road = [[] for _ in range(41) ]
    
    for idx, r in enumerate(routes):
        r[0] = r[0] + 20
        r[1] = r[1] + 20
        
        for i in range(r[0], r[1]+1):
            road[i].append(idx)
    
    road.sort(key=lambda x: len(x), reverse=True)
    
    cars = len(routes)
    
    idx = 0
    
    visited = [True for i in range(len(routes))]
    
    while cars > 0:
        minus = False
        print(road[idx])
        print(visited)
        print(cars)
        for r in road[idx]:
            if visited[r]:
                visited[r] = False
                cars -= 1
                minus = True
                
        if minus:
            answer+=1
            
        idx += 1
        
    return answer

좌표에 숫자 대신 배열을 넣고 route를 idx로 구분시켜서 좌표에 해당하는 idx를 넣는 방식으로 해보려 했다. 그런데

사진처럼 이미 처리된 구간도 값의 크기가 유효해서 매번 카메라로 구간 빠질 때마다 다시 계산하거나 해야할 것 같아서 도저히 방법을 찾지 못했다.

다른 코드 보고 풂

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

다른 블로그를 참고해서 풀었다. 구간은 그대로 두고 카메라를 옮기면서 확인하는 방식이다. 구간 끝을 기준으로 정렬하고 나서 카메라가 구간에 포함되는지를 비교했다. 이렇게 하면 첫번째 구간의 끝에 도달하게되고 그 위치를 기준으로 구간의 시작점 앞에 있는 것들은 스킵되게 된다. 이 방법은 다른 선분 겹치기 문제나 뭐 그런거 풀 때 유용하게 쓰일 것 같다.