[프로그래머스] 탐욕법 6. 단속 카메라

문제

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

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

---

풀이

 

들어온 지점으로 정렬
나간 지점으로 정렬

나간 지점을 기준으로 반복문:
   나간 지점 전에 들어온 지점들 방문처리
   count += 1
   들어온 지점 모두 방문했으면 반복문 탈출

 

근데 뭔가 짜다보니까 visited 안만들어도 되겠다는 생각이 들어서 그냥 해봤다.

def solution(routes):
    answer = 0
    
    start = []
    end = []
    for r in routes:
        start.append(r[0])
        end.append(r[1])
    
    start.sort()
    end.sort()
    
    sIdx = 0
    for e in end:
        if e >= start[sIdx]:
            answer += 1
        while(e >= start[sIdx]):
            sIdx += 1
            if sIdx >= len(routes):
                return answer
    
    return answer

근데 망함

 

그래서 나온 두번째 방법

 

끝나는 지점으로 정렬
끝나는지점을 기준으로 반복문
  해당 지점 이전에 시작된 차량은 routes에서 삭제
  카메라 += 1
route 비었으면 탈출

 

근데 반복문 돌면서 삭제하니까 인덱스 문제가 생길 것 같아 삭제 대신 visited를 만들었다

def solution(routes):
    answer = 0
    visited = [False for _ in range(len(routes))]
    routes = sorted(routes, key = lambda x : x[1])
    
    for i in range(len(routes)):
        flag = False
        if visited[i]:
            continue
        for j in range(len(routes)):
            if routes[i][1] >= routes[j][0] and not visited[j]:
                visited[j] = True
                flag = True
        if flag:
            answer += 1
    
    return answer

뭔가 풀이가 엄청 맘에 안든다

통과하면서도 이게 아닌데,,? 싶었다 ㅠ

 

---

다른 사람의 코드

def solution(routes):
    routes = sorted(routes, key=lambda x: x[1])
    last_camera = -30000

    answer = 0

    for route in routes:
        if last_camera < route[0]: #지난 카메라가 이번 루트를 포함하지 않으면
            answer += 1
            last_camera = route[1] #마지막 카메라 위치 업뎃

    return answer

나가는 지점으로 정렬했으므로

각 나가는 지점에서 있을 수 있는 경우의 수는 두 가지

1. 지난 카메라 이전 또는 동시에 시작함 -> 무시

2. 지난 카메라 이후에 시작함 -> 확인되지 않았으므로 새 카메라 설치

한 것 같다.

 

O(n)에 추가적인 공간도 안썼다.

 

뭔가 예외가 많을 것 같아서 오래 생각했었는데 상황을 단순하게 생각하는 기술?이 부족한 것 같다..