[알고리즘] 프로그래머스 - 단속카메라
문제 설명
https://programmers.co.kr/learn/courses/30/lessons/42884
(처음 생각한) 해결 방안
문제를 보자마자 딱 드는 생각이. 아 전형적인 그리디 문제구나... 정확히 이름은 기억이 안나는데 최대한 수업이 겹치지 않게 교실에 배정하는 그 문제와 비슷한 유형임을 단박에 느낄 수 있었다.
- 자동차들을 진입지점에 대해 오름차순 정렬한다
- 첫 번째 자동차 부터, 나의 진출지점보다 진입지점이 앞서는 자동차들은 나와 같은 카메라를 만난다. 따라서, 나의 진출지점보다 진입지점이 뒤따르는 자동차를 만나는 순간부터 카메라를 새로 설치한다. (카메라 갯수를 늘린다)
- 모든 자동차에 대해 조사가 끝나면 카메라 갯수를 리턴.
결과는 뭐,,, 예시 테케는 운좋게 통과했다만,, 실제 테케는 하나도 맞지 못했다.. 대체 무엇이 문제일까 라고 고민하는 순간 질문 리스트에서 한 테스트 케이스를 만나게 되는데...
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 아닌가? 라는 잘못된 생각을 계속 하고 있었는데,,,
모든 차량이 단속카메라를 만난다
가장 기본인데 차마 떠오르지가 않았다. 단속카메라는 고정된 값에 위치하는데 왜 범위내에 들면 된다고 생각을 했던 것인지... 다행히 오류를 빠르게 찾아냈다.
이것이 '진짜' 입니다
- 자동차들을 진출지점에 대해 오름차순 정렬한다
- 이하 상동
진출시점은 내가 도로에 존재하는 가장 마지막 시점이기 때문에, 다음 차량이 내 진출시점보다 전에 있는지를 판단하기 위해선 진출지점에 대해 정렬을 해야했다. 대체 왜 반대로했지? 회의실 배정 문제 (위에서 말한 뭐 교실 배정 어쩌구) 와 정확히 같은 유형이었다.
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이지?
- 전형적인 유형을 잘 익혀둘 필요가 있을 것 같다.
Author And Source
이 문제에 관하여([알고리즘] 프로그래머스 - 단속카메라), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@grefer/알고리즘-프로그래머스-단속카메라
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
Author And Source
이 문제에 관하여([알고리즘] 프로그래머스 - 단속카메라), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@grefer/알고리즘-프로그래머스-단속카메라저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)