문제 설명

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

(처음 생각한) 해결 방안

문제를 보자마자 딱 드는 생각이. 아 전형적인 그리디 문제구나... 정확히 이름은 기억이 안나는데 최대한 수업이 겹치지 않게 교실에 배정하는 그 문제와 비슷한 유형임을 단박에 느낄 수 있었다.

1. 자동차들을 진입지점에 대해 오름차순 정렬한다
2. 첫 번째 자동차 부터, 나의 진출지점보다 진입지점이 앞서는 자동차들은 나와 같은 카메라를 만난다. 따라서, 나의 진출지점보다 진입지점이 뒤따르는 자동차를 만나는 순간부터 카메라를 새로 설치한다. (카메라 갯수를 늘린다)
3. 모든 자동차에 대해 조사가 끝나면 카메라 갯수를 리턴.

결과는 뭐,,, 예시 테케는 운좋게 통과했다만,, 실제 테케는 하나도 맞지 못했다.. 대체 무엇이 문제일까 라고 고민하는 순간 질문 리스트에서 한 테스트 케이스를 만나게 되는데...

print(solution([[-20,15], [-14,-5], [-18,-13], [-5,-3]])) #2
print(solution([[-20,15], [-20,-15], [-14,-5], [-18,-13], [-5,-3]])) #2

문제를 잘못 이해한 처음 시점에는 두번째의 케이스가 왜 2가 되는지 이해하지 못했다. [-20, 15]가 모든 영역을 커버하니까 1 아닌가? 라는 잘못된 생각을 계속 하고 있었는데,,,

모든 차량이 단속카메라를 만난다

가장 기본인데 차마 떠오르지가 않았다. 단속카메라는 고정된 값에 위치하는데 왜 범위내에 들면 된다고 생각을 했던 것인지... 다행히 오류를 빠르게 찾아냈다.

이것이 '진짜' 입니다

1. 자동차들을 진출지점에 대해 오름차순 정렬한다
2. 이하 상동

진출시점은 내가 도로에 존재하는 가장 마지막 시점이기 때문에, 다음 차량이 내 진출시점보다 전에 있는지를 판단하기 위해선 진출지점에 대해 정렬을 해야했다. 대체 왜 반대로했지? 회의실 배정 문제 (위에서 말한 뭐 교실 배정 어쩌구) 와 정확히 같은 유형이었다.

def solution(routes):
    answer = 0
    routes.sort(key = lambda x: x[1]) # 진출 지점에 대해 정렬!!!!
    val = routes[0][1]
    
    for idx, car in enumerate(routes):
        if val < car[0]:
            answer += 1
            val = routes[idx][1]
            
    return answer+1

Retrospect

• 이게 왜 레벨3이지?
• 전형적인 유형을 잘 익혀둘 필요가 있을 것 같다.